Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)
Dietrich Kuske. A Class of Rational Trace Relations Closed Under Composition. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 20:1-20:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{kuske:LIPIcs.FSTTCS.2023.20, author = {Kuske, Dietrich}, title = {{A Class of Rational Trace Relations Closed Under Composition}}, booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)}, pages = {20:1--20:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-304-1}, ISSN = {1868-8969}, year = {2023}, volume = {284}, editor = {Bouyer, Patricia and Srinivasan, Srikanth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.20}, URN = {urn:nbn:de:0030-drops-193935}, doi = {10.4230/LIPIcs.FSTTCS.2023.20}, annote = {Keywords: rational relations, Mazurkiewicz traces, preservation of rationality and recognizability} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Christopher Hugenroth. Separating Regular Languages over Infinite Words with Respect to the Wagner Hierarchy. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 46:1-46:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{hugenroth:LIPIcs.FSTTCS.2021.46, author = {Hugenroth, Christopher}, title = {{Separating Regular Languages over Infinite Words with Respect to the Wagner Hierarchy}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {46:1--46:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.46}, URN = {urn:nbn:de:0030-drops-155574}, doi = {10.4230/LIPIcs.FSTTCS.2021.46}, annote = {Keywords: Separation, Regular, Wagner Hierarchy, Muller Automata, Parity Automata, Product Automata, Membership} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Dietrich Kuske and Christian Schwarz. Complexity of Counting First-Order Logic for the Subword Order. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 61:1-61:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{kuske_et_al:LIPIcs.MFCS.2020.61, author = {Kuske, Dietrich and Schwarz, Christian}, title = {{Complexity of Counting First-Order Logic for the Subword Order}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {61:1--61:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.61}, URN = {urn:nbn:de:0030-drops-127297}, doi = {10.4230/LIPIcs.MFCS.2020.61}, annote = {Keywords: Counting logic, piecewise testable languages} }
Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)
Alain Finkel and M. Praveen. Verification of Flat FIFO Systems. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{finkel_et_al:LIPIcs.CONCUR.2019.12, author = {Finkel, Alain and Praveen, M.}, title = {{Verification of Flat FIFO Systems}}, booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-121-4}, ISSN = {1868-8969}, year = {2019}, volume = {140}, editor = {Fokkink, Wan and van Glabbeek, Rob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.12}, URN = {urn:nbn:de:0030-drops-109147}, doi = {10.4230/LIPIcs.CONCUR.2019.12}, annote = {Keywords: Infinite state systems, FIFO, counters, flat systems, reachability, termination, complexity} }
Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)
Mario Bravetti, Marco Carbone, Julien Lange, Nobuko Yoshida, and Gianluigi Zavattaro. A Sound Algorithm for Asynchronous Session Subtyping. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bravetti_et_al:LIPIcs.CONCUR.2019.38, author = {Bravetti, Mario and Carbone, Marco and Lange, Julien and Yoshida, Nobuko and Zavattaro, Gianluigi}, title = {{A Sound Algorithm for Asynchronous Session Subtyping}}, booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)}, pages = {38:1--38:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-121-4}, ISSN = {1868-8969}, year = {2019}, volume = {140}, editor = {Fokkink, Wan and van Glabbeek, Rob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.38}, URN = {urn:nbn:de:0030-drops-109408}, doi = {10.4230/LIPIcs.CONCUR.2019.38}, annote = {Keywords: Session types, Concurrency, Subtyping, Algorithm} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Christoph Berkholz and Nicole Schweikardt. Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{berkholz_et_al:LIPIcs.MFCS.2019.58, author = {Berkholz, Christoph and Schweikardt, Nicole}, title = {{Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {58:1--58:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.58}, URN = {urn:nbn:de:0030-drops-110021}, doi = {10.4230/LIPIcs.MFCS.2019.58}, annote = {Keywords: conjunctive queries, constant delay enumeration, hypertree decompositions, submodular width, fixed-parameter tractability} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Nathalie Aubrun, Sebastián Barbieri, and Etienne Moutot. The Domino Problem is Undecidable on Surface Groups. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{aubrun_et_al:LIPIcs.MFCS.2019.46, author = {Aubrun, Nathalie and Barbieri, Sebasti\'{a}n and Moutot, Etienne}, title = {{The Domino Problem is Undecidable on Surface Groups}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {46:1--46:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.46}, URN = {urn:nbn:de:0030-drops-109900}, doi = {10.4230/LIPIcs.MFCS.2019.46}, annote = {Keywords: tilings, substitutions, SFTs, decidability, domino problem} }
Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Faried Abu Zaid, Dietrich Kuske, and Peter Lindner. Climbing up the Elementary Complexity Classes with Theories of Automatic Structures. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 3:1-3:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{abuzaid_et_al:LIPIcs.CSL.2018.3, author = {Abu Zaid, Faried and Kuske, Dietrich and Lindner, Peter}, title = {{Climbing up the Elementary Complexity Classes with Theories of Automatic Structures}}, booktitle = {27th EACSL Annual Conference on Computer Science Logic (CSL 2018)}, pages = {3:1--3:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-088-0}, ISSN = {1868-8969}, year = {2018}, volume = {119}, editor = {Ghica, Dan R. and Jung, Achim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.3}, URN = {urn:nbn:de:0030-drops-96701}, doi = {10.4230/LIPIcs.CSL.2018.3}, annote = {Keywords: Automatic Structures, Complexity Theory, Model Theory} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Dietrich Kuske and Nicole Schweikardt. Gaifman Normal Forms for Counting Extensions of First-Order Logic. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 133:1-133:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{kuske_et_al:LIPIcs.ICALP.2018.133, author = {Kuske, Dietrich and Schweikardt, Nicole}, title = {{Gaifman Normal Forms for Counting Extensions of First-Order Logic}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {133:1--133:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.133}, URN = {urn:nbn:de:0030-drops-91375}, doi = {10.4230/LIPIcs.ICALP.2018.133}, annote = {Keywords: Finite model theory, Gaifman locality, modulo-counting quantifiers, fixed parameter tractable model-checking} }
Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)
Dietrich Kuske, Jiamou Liu, and Anastasia Moskvina. Infinite and Bi-infinite Words with Decidable Monadic Theories. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 472-486, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{kuske_et_al:LIPIcs.CSL.2015.472, author = {Kuske, Dietrich and Liu, Jiamou and Moskvina, Anastasia}, title = {{Infinite and Bi-infinite Words with Decidable Monadic Theories}}, booktitle = {24th EACSL Annual Conference on Computer Science Logic (CSL 2015)}, pages = {472--486}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-90-3}, ISSN = {1868-8969}, year = {2015}, volume = {41}, editor = {Kreutzer, Stephan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.472}, URN = {urn:nbn:de:0030-drops-54325}, doi = {10.4230/LIPIcs.CSL.2015.472}, annote = {Keywords: infinite words, bi-infinite words, monadic second order logic} }
Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Parosh Aziz Abdulla, Mohamed Faouzi Atig, Ahmet Kara, and Othmane Rezine. Verification of Dynamic Register Automata. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 653-665, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{abdulla_et_al:LIPIcs.FSTTCS.2014.653, author = {Abdulla, Parosh Aziz and Atig, Mohamed Faouzi and Kara, Ahmet and Rezine, Othmane}, title = {{Verification of Dynamic Register Automata}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {653--665}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.653}, URN = {urn:nbn:de:0030-drops-48787}, doi = {10.4230/LIPIcs.FSTTCS.2014.653}, annote = {Keywords: Verification, Reachability problem, Register automata} }
Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)
Dietrich Kuske. Isomorphisms of scattered automatic linear orders. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 455-469, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)
@InProceedings{kuske:LIPIcs.CSL.2012.455, author = {Kuske, Dietrich}, title = {{Isomorphisms of scattered automatic linear orders}}, booktitle = {Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL}, pages = {455--469}, 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.455}, URN = {urn:nbn:de:0030-drops-36906}, doi = {10.4230/LIPIcs.CSL.2012.455}, annote = {Keywords: Automatic structures, isomorphism, automorphism} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Dietrich Kuske. Is Ramsey's Theorem omega-automatic?. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 537-548, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{kuske:LIPIcs.STACS.2010.2483, author = {Kuske, Dietrich}, title = {{Is Ramsey's Theorem omega-automatic?}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {537--548}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2483}, URN = {urn:nbn:de:0030-drops-24838}, doi = {10.4230/LIPIcs.STACS.2010.2483}, annote = {Keywords: Logic in computer science, automata, Ramsey theory} }
Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)
Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, and Moshe Y. Vardi. 07441 Abstracts Collection – Algorithmic-Logical Theory of Infinite Structures. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)
@InProceedings{downey_et_al:DagSemProc.07441.1, author = {Downey, Rod and Khoussainov, Bakhadyr and Kuske, Dietrich and Lohrey, Markus and Vardi, Moshe Y.}, title = {{07441 Abstracts Collection – Algorithmic-Logical Theory of Infinite Structures}}, booktitle = {Algorithmic-Logical Theory of Infinite Structures}, pages = {1--13}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {7441}, editor = {Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.1}, URN = {urn:nbn:de:0030-drops-14122}, doi = {10.4230/DagSemProc.07441.1}, annote = {Keywords: Theories of infinite structures , computable model theory and automatic structures , model checking infinite systems} }
Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)
Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, and Moshe Y. Vardi. 07441 Summary – Algorithmic-Logical Theory of Infinite Structures. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)
@InProceedings{downey_et_al:DagSemProc.07441.2, author = {Downey, Rod and Khoussainov, Bakhadyr and Kuske, Dietrich and Lohrey, Markus and Vardi, Moshe Y.}, title = {{07441 Summary – Algorithmic-Logical Theory of Infinite Structures}}, booktitle = {Algorithmic-Logical Theory of Infinite Structures}, pages = {1--2}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {7441}, editor = {Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.2}, URN = {urn:nbn:de:0030-drops-14111}, doi = {10.4230/DagSemProc.07441.2}, annote = {Keywords: Theories of infinite structures , computable model theory and automatic structures , model checking infinite systems} }
Feedback for Dagstuhl Publishing