×

Found 110 Documents (Results 1–100)

100
MathJax

Weighted automata. (English) Zbl 07469502

Pin, Jean-Éric (ed.), Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS). 113-150 (2021).
MSC:  68-XX
PDF BibTeX XML Cite
Full Text: DOI

Communicating automata. (English) Zbl 07425667

Pin, Jean-Éric (ed.), Handbook of automata theory. Volume II. Automata in mathematics and selected applications. Berlin: European Mathematical Society (EMS). 1147-1188 (2021).
MSC:  68Q45
PDF BibTeX XML Cite
Full Text: DOI

Complexity of counting first-order logic for the subword order. (English) Zbl 07559432

Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 61, 12 p. (2020).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Languages ordered by the subword order. (English) Zbl 07158707

Bojańczyk, Mikołaj (ed.) et al., Foundations of software science and computation structures. 22nd international conference, FOSSACS 2019, held as part of the European joint conferences on theory and practice of software, ETAPS 2019, Prague, Czech Republic, April 6–11, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11425, 348-364 (2019).
MSC:  68Nxx 68Qxx
PDF BibTeX XML Cite
Full Text: DOI arXiv

Climbing up the elementary complexity classes with theories of automatic structures. (English) Zbl 07533328

Ghica, Dan R. (ed.) et al., 27th EACSL annual conference on computer science logic, CSL 2018, Birmingham, United Kingdom, September 4–8, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 119, Article 3, 16 p. (2018).
MSC:  03B70
PDF BibTeX XML Cite
Full Text: DOI

Gaifman normal forms for counting extensions of first-order logic. (English) Zbl 07376060

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 133, 14 p. (2018).
MSC:  68Nxx 68Qxx
PDF BibTeX XML Cite
Full Text: DOI

First-order logic with counting: at least, weak Hanf normal forms always exist and can be computed! (English) Zbl 1452.03087

Proceedings of the 2017 32nd annual ACM/IEEE symposium on logic in computer science, LICS 2017, Reykjavík University, Reykjavík, Iceland, June 20–23, 2017. Piscataway, NJ: IEEE Press. Article No. 73, 12 p. (2017).
MSC:  03C80 03C13 68Q60
PDF BibTeX XML Cite
Full Text: arXiv Link

The transformation monoid of a partially lossy queue. (English) Zbl 1489.68063

Weil, Pascal (ed.), Computer science – theory and applications. 12th international computer science symposium in Russia, CSR 2017, Kazan, Russia, June 8–12, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10304, 191-205 (2017).
MSC:  68P05 20M20
PDF BibTeX XML Cite
Full Text: DOI

Multi-buffer simulations for trace language inclusion. (English) Zbl 1478.68130

Cantone, Domenico (ed.) et al., Proceedings of the seventh international symposium on games, automata, logics and formal verification, GandALF 2016, Catania, Italy, September 14–16, 2016. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 226, 213-227 (2016).
MSC:  68Q45 68Q25 91A80
PDF BibTeX XML Cite
Full Text: arXiv Link

Hanf normal form for first-order logic with unary counting quantifiers. (English) Zbl 1394.03061

Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5–8, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4391-6). 277-286 (2016).
PDF BibTeX XML Cite
Full Text: DOI

The trace monoids in the queue monoid and in the direct product of two free monoids. (English) Zbl 1436.68203

Brlek, Srečko (ed.) et al., Developments in language theory. 20th international conference, DLT 2016, Montréal, Canada, July 25–28, 2016. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9840, 256-267 (2016).
MSC:  68Q70 20M05 20M35
PDF BibTeX XML Cite
Full Text: DOI arXiv

Infinite and bi-infinite words with decidable monadic theories. (English) Zbl 1434.03102

Kreutzer, Stephan (ed.), 24th EACSL annual conference and 29th workshop on computer science logic, CSL’15, Berlin, Germany, September 7–10, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 41, 472-486 (2015).
MSC:  03D05 03B16
PDF BibTeX XML Cite
Full Text: DOI

On Presburger arithmetic extended with modulo counting quantifiers. (English) Zbl 1461.03054

Pitts, Andrew (ed.), Foundations of software science and computation structures. 18th international conference, FOSSACS 2015, held as part of the European joint conferences on theory and practice of software, ETAPS 2015, London, UK, April 11–18, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9034, 375-389 (2015).
PDF BibTeX XML Cite
Full Text: DOI Link

The monoid of queue actions. (English) Zbl 1386.68079

Csuhaj-Varjú, Erzsébet (ed.) et al., Mathematical foundations of computer science 2014. 39th international symposium, MFCS 2014, Budapest, Hungary, August 25–29, 2014. Proceedings, Part I. Berlin: Springer (ISBN 978-3-662-44521-1/pbk). Lecture Notes in Computer Science 8634, 340-351 (2014).
PDF BibTeX XML Cite
Full Text: DOI arXiv

The complexity of model checking multi-stack systems. (English) Zbl 1366.68164

Proceedings of the 2013 28th annual ACM/IEEE symposium on logic in computer science, LICS 2013, Tulane University, New Orleans, LA, USA, June 25–28, 2013. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-5020-6). 163-172 (2013).
PDF BibTeX XML Cite
Full Text: DOI

An optimal Gaifman normal form construction for structures of bounded degree. (English) Zbl 1366.03212

Proceedings of the 2013 28th annual ACM/IEEE symposium on logic in computer science, LICS 2013, Tulane University, New Orleans, LA, USA, June 25–28, 2013. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-5020-6). 63-72 (2013).
PDF BibTeX XML Cite
Full Text: DOI

Logical aspects of the lexicographic order on 1-counter languages. (English) Zbl 1400.68109

Chatterjee, Krishnendu (ed.) et al., Mathematical foundations of computer science 2013. 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26–30, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40312-5/pbk). Lecture Notes in Computer Science 8087, 619-630 (2013).
MSC:  68Q45 03D05 03D35
PDF BibTeX XML Cite
Full Text: DOI

Isomorphisms of scattered automatic linear orders. (English) Zbl 1252.03103

Cégielski, Patrick (ed.) et al., Computer science logic (CSL’12). 26th international workshop, 21th annual conference of the EACSL, September 3–6, 2012, Fontainebleau, France. Selected papers based on the presentations at the conference. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-42-2). LIPIcs – Leibniz International Proceedings in Informatics 16, 455-469, electronic only (2012).
MSC:  03D35 03C57
PDF BibTeX XML Cite
Full Text: DOI

(Un)countable and (non)effective versions of Ramsey’s theorem. (English) Zbl 1262.03059

Grohe, Martin (ed.) et al., Model theoretic methods in finite combinatorics. AMS-ASL joint special session, Washington, DC, USA, January 5–8, 2009. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4943-9/pbk). Contemporary Mathematics 558, 467-487 (2011).
MSC:  03D05 05D10
PDF BibTeX XML Cite

Where automatic structures benefit from weighted automata. (English) Zbl 1349.03039

Kuich, Werner (ed.) et al., Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement. Berlin: Springer (ISBN 978-3-642-24896-2/pbk). Lecture Notes in Computer Science 7020, 257-271 (2011).
PDF BibTeX XML Cite
Full Text: DOI

Size and computation of injective tree automatic presentations. (English) Zbl 1343.03029

Murlak, Filip (ed.) et al., Mathematical foundations of computer science 2011. 36th international symposium, MFCS 2011, Warsaw, Poland, August 22–26, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22992-3/pbk). Lecture Notes in Computer Science 6907, 424-435 (2011).
MSC:  03C57 03D05
PDF BibTeX XML Cite
Full Text: DOI

Singular Artin monoids of finite Coxeter type are automatic. (English) Zbl 1295.20062

Dediu, Adrian-Horia (ed.) et al., Language and automata theory and applications. 5th international conference, LATA 2011, Tarragona, Spain, May 26–31, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21253-6/pbk). Lecture Notes in Computer Science 6638, 250-261 (2011).
PDF BibTeX XML Cite
Full Text: DOI

Is Ramsey’s theorem \(\omega\)-automatic? (English) Zbl 1230.03067

Marion, Jean-Yves (ed.) et al., STACS 2010. 27th international symposium on theoretical aspects of computer science, Nancy, France, March 4–6, 2010. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-16-3). LIPIcs – Leibniz International Proceedings in Informatics 5, 537-548, electronic only (2010).
PDF BibTeX XML Cite
Full Text: DOI Link

The isomorphism problem for \(\omega \)-automatic trees. (English) Zbl 1287.03084

Dawar, Anuj (ed.) et al., Computer science logic. 24th international workshop, CSL 2010, 19th annual conference of the EACSL, Brno, Czech Republic, August 23–27, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15204-7/pbk). Lecture Notes in Computer Science 6247, 396-410 (2010).
PDF BibTeX XML Cite
Full Text: DOI Link

Automatic structures of bounded degree revisited. (English) Zbl 1257.03032

Grädel, Erich (ed.) et al., Computer science logic. 23rd international workshop, CSL 2009, 18th annual conference of the EACSL, Coimbra, Portugal, September 7–11, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-04026-9/pbk). Lecture Notes in Computer Science 5771, 364-378 (2009).
MSC:  03B25 03D05 68Q25
PDF BibTeX XML Cite
Full Text: DOI Link

Theories of automatic structures and their complexity. (English) Zbl 1256.03044

Bozapalidis, Symeon (ed.) et al., Algebraic informatics. Third international conference, CAI 2009, Thessaloniki, Greece, May 19–22, 2009, Proceedings. Berlin: Springer (ISBN 978-3-642-03563-0/pbk). Lecture Notes in Computer Science 5725, 81-98 (2009).
PDF BibTeX XML Cite
Full Text: DOI

Compatibility of Shelah and Stupp’s and Muchnik’s iteration with fragments of monadic second order logic. (English) Zbl 1259.03019

Albers, Susanne (ed.) et al., STACS 2008. 25th international symposium on theoretical aspects of computer science, Bordeaux, France, February 21–23, 2008. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-06-4). LIPIcs – Leibniz International Proceedings in Informatics 1, 467-478, electronic only (2008).
MSC:  03B15 03B70
PDF BibTeX XML Cite
Full Text: DOI Link

Construction of tree automata from regular expressions. (English) Zbl 1159.68018

Ito, Masami (ed.) et al., Developments in language theory. 12th international conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85779-2/pbk). Lecture Notes in Computer Science 5257, 491-503 (2008).
MSC:  68Q45
PDF BibTeX XML Cite
Full Text: DOI Numdam

Almost every domain is universal. (English) Zbl 1316.68066

Fiore, Marcelo (ed.), Proceedings of the 23rd conference on the mathematical foundations of programming semantics (MFPS XXIII), New Orleans, LA, USA, April 11–14, 2007. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 173, 103-119 (2007).
MSC:  68Q55 06B35 68Q87
PDF BibTeX XML Cite
Full Text: DOI

Uniform satisfiability in PSPACE for local temporal logics over Mazurkiewicz traces. (English) Zbl 1137.68446

Penczek, Wojciech (ed.) et al., Half a century of inspirational research. Honoring the scientific influence of Antoni Mazurkiewicz. Amsterdam: IOS Press (ISBN 978-1-58603-805-2/pbk). 169-197 (2007).
MSC:  68Q85 03B44 68Q25
PDF BibTeX XML Cite

On communicating automata with bounded channels. (English) Zbl 1137.68447

Penczek, Wojciech (ed.) et al., Half a century of inspirational research. Honoring the scientific influence of Antoni Mazurkiewicz. Amsterdam: IOS Press (ISBN 978-1-58603-805-2/pbk). 147-167 (2007).
MSC:  68Q85 68Q45
PDF BibTeX XML Cite

Propositional dynamic logic for message-passing systems. (English) Zbl 1135.03335

Arvind, V. (ed.) et al., FSTTCS 2007: Foundations of software technology and theoretical computer science. 27th international conference, New Delhi, India, December 12–14, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-77049-7/pbk). Lecture Notes in Computer Science 4855, 303-315 (2007).
MSC:  03B70 68Q60 68Q85
PDF BibTeX XML Cite
Full Text: DOI arXiv

First-order and counting theories of \(\omega\)-automatic structures. (English) Zbl 1138.03032

Aceto, Luca (ed.) et al., Foundations of software science and computation structures. 9th international conference, FOSSACS 2006, held as part of the joint European conferences on theory and practice of software, ETAPS 2006, Vienna, Austria, March 25–31, 2006. Proceedings. Berlin: Springer (ISBN 3-540-33045-3/pbk). Lecture Notes in Computer Science 3921, 322-336 (2006).
MSC:  03D05 03B25 03C80
PDF BibTeX XML Cite
Full Text: DOI

Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces. (English) Zbl 1134.68436

Abadi, Martín (ed.) et al., CONCUR 2005 – concurrency theory. 16th international conference, CONCUR 2005, San Francisco, CA, USA, August 23–26, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28309-9/pbk). Lecture Notes in Computer Science 3653, 533-547 (2005).
MSC:  68Q85 03B44 68Q25
PDF BibTeX XML Cite
Full Text: DOI

Snapshot verification. (English) Zbl 1087.68055

Halbwachs, Nicolas (ed.) et al., Tools and algorithms for the construction and analysis of systems. 11th international conference, TACAS 2005, held as part of the joint European conference on theory and practice of software, ETAPS 2005, Edinburgh, UK, April 4–8, 2005. Proceedings. Berlin: Springer (ISBN 3-540-25333-5/pbk). Lecture Notes in Computer Science 3440, 510-525 (2005).
MSC:  68Q60 68Q85
PDF BibTeX XML Cite
Full Text: DOI

A Kleene theorem for a class of communicating automata with effective algorithms. (English) Zbl 1117.68403

Calude, Cristian S. (ed.) et al., Developments in language theory. 8th international conference, DLT 2004, Auckland, New Zealand, December 13–17, 2004. Proceedings. Berlin: Springer (ISBN 3-540-24014-4/pbk). Lecture Notes in Computer Science 3340, 30-48 (2004).
MSC:  68Q45 68Q85
PDF BibTeX XML Cite
Full Text: DOI

The role of the complementarity relation in Watson-Crick automata and sticker systems. (English) Zbl 1117.68407

Calude, Cristian S. (ed.) et al., Developments in language theory. 8th international conference, DLT 2004, Auckland, New Zealand, December 13–17, 2004. Proceedings. Berlin: Springer (ISBN 3-540-24014-4/pbk). Lecture Notes in Computer Science 3340, 272-283 (2004).
MSC:  68Q45 68Q05
PDF BibTeX XML Cite
Full Text: DOI

Branching automata with costs – a way of reflecting parallelism in costs. (English) Zbl 1279.68162

Ibarra, Oscar H. (ed.) et al., Implementation and application of automata. 8th international conference, CIAA 2003, Santa Barbara, CA, USA, July 16–18, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40561-5/pbk). Lect. Notes Comput. Sci. 2759, 150-162 (2003).
MSC:  68Q45
PDF BibTeX XML Cite
Full Text: DOI Link

Satisfiability and model checking for MSO-definable temporal logics are in PSPACE. (English) Zbl 1195.68068

Amadio, Roberto (ed.) et al., CONCUR 2003 – concurrency theory. 14th international conference, Marseille, France, September 3–5, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40753-7/pbk). Lect. Notes Comput. Sci. 2761, 222-236 (2003).
PDF BibTeX XML Cite
Full Text: DOI

Is Cantor’s theorem automatic? (English) Zbl 1273.03124

Vardi, Moshe Y. (ed.) et al., Logic for programming, artificial intelligence, and reasoning. 10th international conference, LPAR 2003, Almaty, Kazakhstan, September 22–26, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20101-7/pbk). Lect. Notes Comput. Sci. 2850, 332-345 (2003).
MSC:  03C57 03D05 06A05
PDF BibTeX XML Cite

Skew and infinitary formal power series. (English) Zbl 1039.68065

Baeten, Jos C. M. (ed.) et al., Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 – July 4, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40493-7/pbk). Lect. Notes Comput. Sci. 2719, 426-438 (2003).
MSC:  68Q45
PDF BibTeX XML Cite
Full Text: Link

Decidable theories of Cayley-graphs. (English) Zbl 1036.03009

Alt, Helmut (ed.) et al., STACS 2003. 20th annual symposium of theoretical aspects on computer science, Berlin, Germany, February 27 – March 1, 2003. Proceedings. Berlin: Springer (ISBN 3-540-00623-0/pbk). Lect. Notes Comput. Sci. 2607, 463-474 (2003).
MSC:  03B25 05C25 20F10
PDF BibTeX XML Cite
Full Text: Link

Recognizable sets of N-free pomsets are monadically axiomatizable. (English) Zbl 1073.03022

Kuich, Werner (ed.) et al., Developments in language theory. 5th international conference, DLT 2001, Wien, Austria, July 16–21, 2001. Revised papers. Berlin: Springer (ISBN 3-540-43453-4). Lect. Notes Comput. Sci. 2295, 206-216 (2002).
PDF BibTeX XML Cite
Full Text: Link

On the theory of one-step rewriting in trace monoids. (English) Zbl 1057.68045

Widmayer, Peter (ed.) et al., Automata, languages and programming. 29th international colloquium, ICALP 2002, Málaga, Spain, July 8–13, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43864-5). Lect. Notes Comput. Sci. 2380, 752-763 (2002).
MSC:  68Q42
PDF BibTeX XML Cite
Full Text: Link

A further step towards a theory of regular MSC languages. (English) Zbl 1054.68538

Alt, Helmut (ed.) et al., STACS 2002. 19th annual symposium on theoretical aspects of computer science. Antibes - Juan les Pins, France, March 14–16, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43283-3). Lect. Notes Comput. Sci. 2285, 489-500 (2002).
MSC:  68N30 68Q45 03D05
PDF BibTeX XML Cite
Full Text: Link

Some relatives of automatic and hyperbolic groups. (English) Zbl 1031.20047

Gomes, Gracinda M. S. (ed.) et al., Semigroups, algorithms, automata and languages. Proceedings of workshops held at the International Centre of Mathematics, CIM, Coimbra, Portugal, May, June and July 2001. Singapore: World Scientific. 379-406 (2002).
MSC:  20M05 20F67
PDF BibTeX XML Cite

A model theoretic proof of Büchi-type theorems and first-order logic for N-free pomsets. (English) Zbl 0976.03045

Ferreira, Afonso (ed.) et al., STACS 2001. 18th annual symposium on theoretical aspects of computer science. Dresden, Germany, February 15-17, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2010, 443-454 (2001).
MSC:  03D05 03C98 68Q45
PDF BibTeX XML Cite
Full Text: Link

Pomsets for local trace languages – recognizability, logic \(\&\) Petri nets. (English) Zbl 0999.68530

Palamidessi, Catuscia (ed.), CONCUR 2000 - Concurrency theory. 11th international conference, University Park, PA, USA, August 22-25, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1877, 426-441 (2000).
MSC:  68Q85 68Q45 03D05
PDF BibTeX XML Cite

The boundary between decidable and undecidable fragments of the fluent calculus. (English) Zbl 0988.68179

Parigot, Michel (ed.) et al., Logic for programming and automated reasoning. 7th international conference, LPAR 2000, Reunion Island, France, November 6-10, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1955, 436-450 (2000).
MSC:  68T27 03B25
PDF BibTeX XML Cite

Filter Results by …

Document Type

Reviewing State

all top 5

Year of Publication

all top 3

Classification

Software