Published in: Dagstuhl Reports, Volume 11, Issue 10 (2022)
Thomas Colcombet, Karin Quaas, and Michał Skrzypczak. Unambiguity in Automata Theory (Dagstuhl Seminar 21452). In Dagstuhl Reports, Volume 11, Issue 10, pp. 57-71, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@Article{colcombet_et_al:DagRep.11.10.57, author = {Colcombet, Thomas and Quaas, Karin and Skrzypczak, Micha{\l}}, title = {{Unambiguity in Automata Theory (Dagstuhl Seminar 21452)}}, pages = {57--71}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {11}, number = {10}, editor = {Colcombet, Thomas and Quaas, Karin and Skrzypczak, Micha{\l}}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.10.57}, URN = {urn:nbn:de:0030-drops-159282}, doi = {10.4230/DagRep.11.10.57}, annote = {Keywords: Unambiguity in Automata Theory, Dagstuhl Seminar} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Damian Niwiński and Michał Skrzypczak. On Guidable Index of Tree Automata. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 81:1-81:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{niwinski_et_al:LIPIcs.MFCS.2021.81, author = {Niwi\'{n}ski, Damian and Skrzypczak, Micha{\l}}, title = {{On Guidable Index of Tree Automata}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {81:1--81:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.81}, URN = {urn:nbn:de:0030-drops-145214}, doi = {10.4230/LIPIcs.MFCS.2021.81}, annote = {Keywords: guidable automata, index problem, \omega-regular games} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Lorenzo Clemente and Michał Skrzypczak. Deterministic and Game Separability for Regular Languages of Infinite Trees. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 126:1-126:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{clemente_et_al:LIPIcs.ICALP.2021.126, author = {Clemente, Lorenzo and Skrzypczak, Micha{\l}}, title = {{Deterministic and Game Separability for Regular Languages of Infinite Trees}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {126:1--126:15}, 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.126}, URN = {urn:nbn:de:0030-drops-141952}, doi = {10.4230/LIPIcs.ICALP.2021.126}, annote = {Keywords: separation, infinite trees, regular languages, deterministic automata, game automata} }
Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)
Alexander Rabinovich and Doron Tiferet. Degrees of Ambiguity for Parity Tree Automata. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 36:1-36:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{rabinovich_et_al:LIPIcs.CSL.2021.36, author = {Rabinovich, Alexander and Tiferet, Doron}, title = {{Degrees of Ambiguity for Parity Tree Automata}}, booktitle = {29th EACSL Annual Conference on Computer Science Logic (CSL 2021)}, pages = {36:1--36:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-175-7}, ISSN = {1868-8969}, year = {2021}, volume = {183}, editor = {Baier, Christel and Goubault-Larrecq, Jean}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.36}, URN = {urn:nbn:de:0030-drops-134709}, doi = {10.4230/LIPIcs.CSL.2021.36}, annote = {Keywords: automata on infinite trees, degree of ambiguity, omega word automata, parity automata} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Udi Boker, Denis Kuperberg, Karoliina Lehtinen, and Michał Skrzypczak. On the Succinctness of Alternating Parity Good-For-Games Automata. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 41:1-41:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{boker_et_al:LIPIcs.FSTTCS.2020.41, author = {Boker, Udi and Kuperberg, Denis and Lehtinen, Karoliina and Skrzypczak, Micha{\l}}, title = {{On the Succinctness of Alternating Parity Good-For-Games Automata}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {41:1--41:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.41}, URN = {urn:nbn:de:0030-drops-132825}, doi = {10.4230/LIPIcs.FSTTCS.2020.41}, annote = {Keywords: Good for games, history-determinism, alternation} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Vincent Michielini and Michał Skrzypczak. Regular Choice Functions and Uniformisations For countable Domains. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 69:1-69:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{michielini_et_al:LIPIcs.MFCS.2020.69, author = {Michielini, Vincent and Skrzypczak, Micha{\l}}, title = {{Regular Choice Functions and Uniformisations For countable Domains}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {69:1--69:13}, 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.69}, URN = {urn:nbn:de:0030-drops-127386}, doi = {10.4230/LIPIcs.MFCS.2020.69}, annote = {Keywords: Uniformisation, Monadic Second-order logic, Countable words} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Alexander Rabinovich and Doron Tiferet. Ambiguity Hierarchy of Regular Infinite Tree Languages. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 80:1-80:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{rabinovich_et_al:LIPIcs.MFCS.2020.80, author = {Rabinovich, Alexander and Tiferet, Doron}, title = {{Ambiguity Hierarchy of Regular Infinite Tree Languages}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {80:1--80:14}, 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.80}, URN = {urn:nbn:de:0030-drops-127495}, doi = {10.4230/LIPIcs.MFCS.2020.80}, annote = {Keywords: automata on infinite trees, ambiguous automata, monadic second-order logic} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Damian Niwiński, Marcin Przybyłko, and Michał Skrzypczak. Computing Measures of Weak-MSO Definable Sets of Trees. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 136:1-136:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{niwinski_et_al:LIPIcs.ICALP.2020.136, author = {Niwi\'{n}ski, Damian and Przyby{\l}ko, Marcin and Skrzypczak, Micha{\l}}, title = {{Computing Measures of Weak-MSO Definable Sets of Trees}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {136:1--136:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.136}, URN = {urn:nbn:de:0030-drops-125430}, doi = {10.4230/LIPIcs.ICALP.2020.136}, annote = {Keywords: infinite trees, weak alternating automata, coin-flipping measure} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Nathan Lhote, Vincent Michielini, and Michał Skrzypczak. Uniformisation Gives the Full Strength of Regular Languages. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 61:1-61:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{lhote_et_al:LIPIcs.MFCS.2019.61, author = {Lhote, Nathan and Michielini, Vincent and Skrzypczak, Micha{\l}}, title = {{Uniformisation Gives the Full Strength of Regular Languages}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {61:1--61:13}, 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.61}, URN = {urn:nbn:de:0030-drops-110053}, doi = {10.4230/LIPIcs.MFCS.2019.61}, annote = {Keywords: pseudo-variety, finite word, semigroup, uniformisation, regular language} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Michal Skrzypczak. Unambiguous Languages Exhaust the Index Hierarchy. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 140:1-140:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{skrzypczak:LIPIcs.ICALP.2018.140, author = {Skrzypczak, Michal}, title = {{Unambiguous Languages Exhaust the Index Hierarchy}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {140:1--140: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.140}, URN = {urn:nbn:de:0030-drops-91442}, doi = {10.4230/LIPIcs.ICALP.2018.140}, annote = {Keywords: unambiguous automata, parity games, infinite trees, index hierarchy} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Udi Boker, Orna Kupferman, and Michal Skrzypczak. How Deterministic are Good-For-Games Automata?. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 18:1-18:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{boker_et_al:LIPIcs.FSTTCS.2017.18, author = {Boker, Udi and Kupferman, Orna and Skrzypczak, Michal}, title = {{How Deterministic are Good-For-Games Automata?}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {18:1--18:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.18}, URN = {urn:nbn:de:0030-drops-83776}, doi = {10.4230/LIPIcs.FSTTCS.2017.18}, annote = {Keywords: finite automata on infinite words, determinism, good-for-games} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Filippo Cavallari, Henryk Michalewski, and Michal Skrzypczak. A Characterisation of Pi^0_2 Regular Tree Languages. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 56:1-56:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{cavallari_et_al:LIPIcs.MFCS.2017.56, author = {Cavallari, Filippo and Michalewski, Henryk and Skrzypczak, Michal}, title = {{A Characterisation of Pi^0\underline2 Regular Tree Languages}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {56:1--56:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.56}, URN = {urn:nbn:de:0030-drops-80683}, doi = {10.4230/LIPIcs.MFCS.2017.56}, annote = {Keywords: infinite trees, Rabin-Mostowski hierarchy, regular languages} }
Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)
Leszek Aleksander Kolodziejczyk, Henryk Michalewski, Pierre Pradic, and Michal Skrzypczak. The Logical Strength of Büchi's Decidability Theorem. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 36:1-36:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{kolodziejczyk_et_al:LIPIcs.CSL.2016.36, author = {Kolodziejczyk, Leszek Aleksander and Michalewski, Henryk and Pradic, Pierre and Skrzypczak, Michal}, title = {{The Logical Strength of B\"{u}chi's Decidability Theorem}}, booktitle = {25th EACSL Annual Conference on Computer Science Logic (CSL 2016)}, pages = {36:1--36:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-022-4}, ISSN = {1868-8969}, year = {2016}, volume = {62}, editor = {Talbot, Jean-Marc and Regnier, Laurent}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.36}, URN = {urn:nbn:de:0030-drops-65765}, doi = {10.4230/LIPIcs.CSL.2016.36}, annote = {Keywords: nondeterministic automata, monadic second-order logic, B\"{u}chi's theorem, additive Ramsey's theorem, reverse mathematics} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Michal Skrzypczak and Igor Walukiewicz. Deciding the Topological Complexity of Büchi Languages. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 99:1-99:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{skrzypczak_et_al:LIPIcs.ICALP.2016.99, author = {Skrzypczak, Michal and Walukiewicz, Igor}, title = {{Deciding the Topological Complexity of B\"{u}chi Languages}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {99:1--99:13}, 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.99}, URN = {urn:nbn:de:0030-drops-62346}, doi = {10.4230/LIPIcs.ICALP.2016.99}, annote = {Keywords: tree automata, non-determinism, Borel sets, topological complexity, decidability} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Marcin Przybylko and Michal Skrzypczak. On the Complexity of Branching Games with Regular Conditions. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 78:1-78:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{przybylko_et_al:LIPIcs.MFCS.2016.78, author = {Przybylko, Marcin and Skrzypczak, Michal}, title = {{On the Complexity of Branching Games with Regular Conditions}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {78:1--78:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.78}, URN = {urn:nbn:de:0030-drops-64865}, doi = {10.4230/LIPIcs.MFCS.2016.78}, annote = {Keywords: stochastic games, meta-parity games, infinite trees, regular languages, parity automata} }
Feedback for Dagstuhl Publishing