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 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 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} }
Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)
Markus Lohrey. Application of verification techniques to inverse monoids. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)
@InProceedings{lohrey:DagSemProc.07441.3, author = {Lohrey, Markus}, title = {{Application of verification techniques to inverse monoids}}, booktitle = {Algorithmic-Logical Theory of Infinite Structures}, pages = {1--15}, 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.3}, URN = {urn:nbn:de:0030-drops-14109}, doi = {10.4230/DagSemProc.07441.3}, annote = {Keywords: Inverse monoids, word problems, Cayley-graphs, complexity} }
Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)
Dietrich Kuske. Compatibility of Shelah and Stupp's and of Muchnik's iteration with fragments of monadic second order logic. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)
@InProceedings{kuske:DagSemProc.07441.4, author = {Kuske, Dietrich}, title = {{Compatibility of Shelah and Stupp's and of Muchnik's iteration with fragments of monadic second order logic}}, booktitle = {Algorithmic-Logical Theory of Infinite Structures}, pages = {1--14}, 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.4}, URN = {urn:nbn:de:0030-drops-14078}, doi = {10.4230/DagSemProc.07441.4}, annote = {Keywords: Logic in computer science, Rabin's tree theorem} }
Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)
Stefan Göller, Markus Lohrey, and Carsten Lutz. PDL with Intersection and Converse is 2EXP-complete. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)
@InProceedings{goller_et_al:DagSemProc.07441.5, author = {G\"{o}ller, Stefan and Lohrey, Markus and Lutz, Carsten}, title = {{PDL with Intersection and Converse is 2EXP-complete}}, booktitle = {Algorithmic-Logical Theory of Infinite Structures}, pages = {1--17}, 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.5}, URN = {urn:nbn:de:0030-drops-14093}, doi = {10.4230/DagSemProc.07441.5}, annote = {Keywords: Satisfiability, Propositional Dynamic Logic, Computational Complexity} }
Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)
Thierry Cachat. Tree Automata Make Ordinal Theory Easy. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)
@InProceedings{cachat:DagSemProc.07441.6, author = {Cachat, Thierry}, title = {{Tree Automata Make Ordinal Theory Easy}}, booktitle = {Algorithmic-Logical Theory of Infinite Structures}, pages = {1--11}, 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.6}, URN = {urn:nbn:de:0030-drops-14082}, doi = {10.4230/DagSemProc.07441.6}, annote = {Keywords: Ordinals, First Order theory, Monadic Second Order Theory, tree automata} }
Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
Dietrich Kuske. Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 467-478, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)
@InProceedings{kuske:LIPIcs.STACS.2008.1366, author = {Kuske, Dietrich}, title = {{Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {467--478}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1366}, URN = {urn:nbn:de:0030-drops-13668}, doi = {10.4230/LIPIcs.STACS.2008.1366}, annote = {Keywords: Logic in computer science, Rabin's tree theorem} }
Feedback for Dagstuhl Publishing