Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Dominik D. Freydenberger and Liat Peterfreund. The Theory of Concatenation over Finite Models. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 130:1-130:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{freydenberger_et_al:LIPIcs.ICALP.2021.130, author = {Freydenberger, Dominik D. and Peterfreund, Liat}, title = {{The Theory of Concatenation over Finite Models}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {130:1--130:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.130}, URN = {urn:nbn:de:0030-drops-141997}, doi = {10.4230/LIPIcs.ICALP.2021.130}, annote = {Keywords: finite model theory, word equations, descriptive complexity, model checking, document spanners} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Lukas Fleischer and Manfred Kufleitner. Testing Simon's congruence. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 62:1-62:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{fleischer_et_al:LIPIcs.MFCS.2018.62, author = {Fleischer, Lukas and Kufleitner, Manfred}, title = {{Testing Simon's congruence}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {62:1--62:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.62}, URN = {urn:nbn:de:0030-drops-96445}, doi = {10.4230/LIPIcs.MFCS.2018.62}, annote = {Keywords: regular language, scattered subword, piecewise testability, string algorithm} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Lukas Fleischer and Manfred Kufleitner. The Intersection Problem for Finite Monoids. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{fleischer_et_al:LIPIcs.STACS.2018.30, author = {Fleischer, Lukas and Kufleitner, Manfred}, title = {{The Intersection Problem for Finite Monoids}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {30:1--30:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.30}, URN = {urn:nbn:de:0030-drops-85079}, doi = {10.4230/LIPIcs.STACS.2018.30}, annote = {Keywords: intersection problem, finite monoid, recognizing morphism, complexity} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Volker Diekert, Artur Jez, and Manfred Kufleitner. Solutions of Word Equations Over Partially Commutative Structures. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 127:1-127:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{diekert_et_al:LIPIcs.ICALP.2016.127, author = {Diekert, Volker and Jez, Artur and Kufleitner, Manfred}, title = {{Solutions of Word Equations Over Partially Commutative Structures}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {127:1--127:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.127}, URN = {urn:nbn:de:0030-drops-62624}, doi = {10.4230/LIPIcs.ICALP.2016.127}, annote = {Keywords: Word equations, EDT0L language, trace monoid, right-angled Artin group, partial commutation} }
Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Lukas Fleischer and Manfred Kufleitner. Efficient Algorithms for Morphisms over Omega-Regular Languages. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 112-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{fleischer_et_al:LIPIcs.FSTTCS.2015.112, author = {Fleischer, Lukas and Kufleitner, Manfred}, title = {{Efficient Algorithms for Morphisms over Omega-Regular Languages}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {112--124}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.112}, URN = {urn:nbn:de:0030-drops-56200}, doi = {10.4230/LIPIcs.FSTTCS.2015.112}, annote = {Keywords: B\"{u}chi automata, omega-regular language, syntactic semigroup, recognizing morphism, MSO} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Martin Huschenbett and Manfred Kufleitner. Ehrenfeucht-Fraïssé Games on Omega-Terms. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 374-385, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{huschenbett_et_al:LIPIcs.STACS.2014.374, author = {Huschenbett, Martin and Kufleitner, Manfred}, title = {{Ehrenfeucht-Fra\"{i}ss\'{e} Games on Omega-Terms}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {374--385}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.374}, URN = {urn:nbn:de:0030-drops-44729}, doi = {10.4230/LIPIcs.STACS.2014.374}, annote = {Keywords: regular language, first-order logic, finite monoid, Ehrenfeucht-Fra\"{i}ss\'{e} games, pseudoidentity} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Manfred Kufleitner and Alexander Lauser. Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 305-316, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{kufleitner_et_al:LIPIcs.STACS.2013.305, author = {Kufleitner, Manfred and Lauser, Alexander}, title = {{Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {305--316}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.305}, URN = {urn:nbn:de:0030-drops-39438}, doi = {10.4230/LIPIcs.STACS.2013.305}, annote = {Keywords: automata theory, semigroups, regular languages, first-order logic} }
Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)
Manfred Kufleitner and Pascal Weil. The FO2 alternation hierarchy is decidable. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 426-439, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{kufleitner_et_al:LIPIcs.CSL.2012.426, author = {Kufleitner, Manfred and Weil, Pascal}, title = {{The FO2 alternation hierarchy is decidable}}, booktitle = {Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL}, pages = {426--439}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-42-2}, ISSN = {1868-8969}, year = {2012}, volume = {16}, editor = {C\'{e}gielski, Patrick and Durand, Arnaud}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.426}, URN = {urn:nbn:de:0030-drops-36888}, doi = {10.4230/LIPIcs.CSL.2012.426}, annote = {Keywords: first-order logic, regular language, automata theory, semigroup, ranker} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Jakub Kallas, Manfred Kufleitner, and Alexander Lauser. First-order Fragments with Successor over Infinite Words. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 356-367, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{kallas_et_al:LIPIcs.STACS.2011.356, author = {Kallas, Jakub and Kufleitner, Manfred and Lauser, Alexander}, title = {{First-order Fragments with Successor over Infinite Words}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {356--367}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.356}, URN = {urn:nbn:de:0030-drops-30267}, doi = {10.4230/LIPIcs.STACS.2011.356}, annote = {Keywords: infinite words, regular languages, first-order logic, automata theory, semi-groups, topology} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Volker Diekert and Manfred Kufleitner. Fragments of First-Order Logic over Infinite Words. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 325-336, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{diekert_et_al:LIPIcs.STACS.2009.1818, author = {Diekert, Volker and Kufleitner, Manfred}, title = {{Fragments of First-Order Logic over Infinite Words}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {325--336}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1818}, URN = {urn:nbn:de:0030-drops-18185}, doi = {10.4230/LIPIcs.STACS.2009.1818}, annote = {Keywords: Infinite words, Regular languages, First-order logic, Automata theory, Semigroups, Topology} }