×

Found 260 Documents (Results 1–100)

First-order separation over countable ordinals. (English) Zbl 07793033

Bouyer, Patricia (ed.) et al., Foundations of software science and computation structures. 25th international conference, FOSSACS 2022, held as part of the European joint conferences on theory and practice of software, ETAPS 2022, Munich, Germany, April 2–7, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13242, 264-284 (2022).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Operations on subregular languages and nondeterministic state complexity. (English) Zbl 07643467

Han, Yo-Sub (ed.) et al., Descriptional complexity of formal systems. 24th IFIP WG 1.02 international conference, DCFS 2022, Debrecen, Hungary, August 29–31, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13439, 112-126 (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Closure properties of subregular languages under operations. (English) Zbl 07630825

Durand-Lose, Jérôme (ed.) et al., Machines, computations, and universality. 9th international conference, MCU 2022, Debrecen, Hungary, August 31 – September 2, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13419, 126-142 (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Learning from positive and negative examples: dichotomies and parameterized algorithms. (English) Zbl 07577714

Bazgan, Cristina (ed.) et al., Combinatorial algorithms. 33rd international workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13270, 398-411 (2022).
MSC:  68Rxx 68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Deciding FO-definability of regular languages. (English) Zbl 07670522

Fahrenberg, Uli (ed.) et al., Relational and algebraic methods in computer science. 19th international conference, RAMiCS 2021, Marseille, France, November 2–5, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13027, 241-257 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

State complexity investigations on commutative languages – the upward and downward closure, commutative aperiodic and commutative group languages. (English) Zbl 07614742

Han, Yo-Sub (ed.) et al., Descriptional complexity of formal systems. 23rd IFIP WG 1.02 international conference, DCFS 2021, virtual event, September 5, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13037, 64-75 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Weighted automata. (English) Zbl 1508.68189

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

Wreath/cascade products and related decomposition results for the concurrent setting of Mazurkiewicz traces. (English) Zbl 07559475

Konnov, Igor (ed.) et al., 31st international conference on concurrency theory. CONCUR 2020, September 1–4, 2020, Vienna, Austria, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 171, Article 19, 17 p. (2020).
MSC:  68Q85
PDFBibTeX XMLCite
Full Text: DOI arXiv

From equational specifications of algebras with structure to varieties of data languages (invited paper). (English) Zbl 07649885

Roggenbach, Markus (ed.) et al., 8th conference on algebra and coalgebra in computer science, CALCO 2019, London, United Kingdom, June 3–6, 2019. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 139, Article 2, 5 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Aperiodic weighted automata and weighted first-order logic. (English) Zbl 07561720

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 76, 15 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Uniformisation gives the full strength of regular languages. (English) Zbl 07561705

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 61, 13 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

The quantifier alternation hierarchy of synchronous relations. (English) Zbl 07561673

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 29, 14 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Varieties of data languages. (English) Zbl 07561623

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 130, 14 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

On all things star-free. (English) Zbl 07561619

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 126, 14 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

On canonical models for rational functions over infinite words. (English) Zbl 1528.68181

Ganguly, Sumit (ed.) et al., 38th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2018, Ahmedabad, India, December 11–13, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 122, Article 30, 17 p. (2018).
MSC:  68Q45 03D05
PDFBibTeX XMLCite
Full Text: DOI

An algebraic decision procedure for two-variable logic with a between relation. (English) Zbl 1528.03091

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 28, 17 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

Backward deterministic Büchi automata on infinite words. (English) Zbl 1491.68103

Lokam, Satya (ed.) et al., 37th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2017, IIT Kanpur, India, December 12–14, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 93, Article 6, 9 p. (2018).
MSC:  68Q45 03B44 03D05
PDFBibTeX XMLCite
Full Text: DOI

Rational, recognizable, and aperiodic sets in the partially lossy queue monoid. (English) Zbl 1487.68162

Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 96, Article 45, 14 p. (2018).
MSC:  68Q70 03D05 20M35
PDFBibTeX XMLCite
Full Text: DOI

The intersection problem for finite monoids. (English) Zbl 1487.68161

Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 96, Article 30, 14 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Eilenberg theorems for free. (English) Zbl 1441.68139

Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 43, 15 p. (2017).
MSC:  68Q70
PDFBibTeX XMLCite
Full Text: DOI arXiv

Concatenation hierarchies: new bottle, old wine. (English) Zbl 1489.68134

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, 25-37 (2017).
MSC:  68Q45 68-02 68-03
PDFBibTeX XMLCite
Full Text: DOI

Problems on finite automata and the exponential time hypothesis. (English) Zbl 1475.68152

Han, Yo-Sub (ed.) et al., Implementation and application of automata. 21st international conference, CIAA 2016, Seoul, South Korea, July 19–22, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9705, 89-100 (2016).
MSC:  68Q45 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Characterization of the pseudovariety generated by finite monoids satisfying \(\mathcal R=\mathcal H\). (English. Russian original) Zbl 1344.20074

Proc. Steklov Inst. Math. 292, Suppl. 1, S245-S252 (2016); translation from Tr. Inst. Mat. Mekh. (Ekaterinburg) 21, No. 1, 197-204 (2015).
MSC:  20M10 20M07
PDFBibTeX XMLCite
Full Text: DOI

The word problem for omega-terms over the Trotter-Weil hierarchy (extended abstract). (English) Zbl 1386.20037

Kulikov, Alexander S. (ed.) et al., Computer science – theory and applications. 11th international computer science symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9–13, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-34170-5/pbk; 978-3-319-34171-2/ebook). Lecture Notes in Computer Science 9691, 237-250 (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Profinite monads, profinite equations, and Reiterman’s theorem. (English) Zbl 1474.18010

Jacobs, Bart (ed.) et al., Foundations of software science and computation structures. 19th international conference, FOSSACS 2016, held as part of the European joint conferences on theory and practice of software, ETAPS 2016, Eindhoven, The Netherlands, April 2–8, 2016. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9634, 531-547 (2016).
MSC:  18C15 68Q70 08B25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Quantifier alternation for infinite words. (English) Zbl 1476.03051

Jacobs, Bart (ed.) et al., Foundations of software science and computation structures. 19th international conference, FOSSACS 2016, held as part of the European joint conferences on theory and practice of software, ETAPS 2016, Eindhoven, The Netherlands, April 2–8, 2016. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9634, 234-251 (2016).
MSC:  03D05 03B70 03D15
PDFBibTeX XMLCite
Full Text: DOI arXiv

On decidability of intermediate levels of concatenation hierarchies. (English) Zbl 1434.68224

Potapov, Igor (ed.), Developments in language theory. 19th international conference, DLT 2015, Liverpool, UK, July 27–30, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9168, 58-70 (2015).
MSC:  68Q45 03B25
PDFBibTeX XMLCite
Full Text: DOI Link

Limited set quantifiers over countable linear orderings. (English) Zbl 1443.03006

Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part II. Berlin: Springer. Lect. Notes Comput. Sci. 9135, 146-158 (2015).
MSC:  03B16 03B25 06A05
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

Biographic Reference

all top 3

Software