Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Robert Ferens and Marek Szykuła. Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 59:1-59:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ferens_et_al:LIPIcs.ICALP.2023.59, author = {Ferens, Robert and Szyku{\l}a, Marek}, title = {{Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {59:1--59:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.59}, URN = {urn:nbn:de:0030-drops-181110}, doi = {10.4230/LIPIcs.ICALP.2023.59}, annote = {Keywords: \v{C}ern\'{y} conjecture, complete reachability, DFA, extending word, reachability, reset threshold, reset word, simple idempotent, synchronizing automaton, synchronizing word} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Marek Szykuła and Adam Zyzik. An Improved Algorithm for Finding the Shortest Synchronizing Words. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 85:1-85:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{szykula_et_al:LIPIcs.ESA.2022.85, author = {Szyku{\l}a, Marek and Zyzik, Adam}, title = {{An Improved Algorithm for Finding the Shortest Synchronizing Words}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {85:1--85:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.85}, URN = {urn:nbn:de:0030-drops-170237}, doi = {10.4230/LIPIcs.ESA.2022.85}, annote = {Keywords: \v{C}ern\{\'{y}\} conjecture, reset threshold, reset word, subset checking, synchronizing automaton, synchronizing word} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Robert Ferens, Marek Szykuła, and Vojtěch Vorel. Lower Bounds on Avoiding Thresholds. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 46:1-46:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{ferens_et_al:LIPIcs.MFCS.2021.46, author = {Ferens, Robert and Szyku{\l}a, Marek and Vorel, Vojt\v{e}ch}, title = {{Lower Bounds on Avoiding Thresholds}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {46:1--46: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.46}, URN = {urn:nbn:de:0030-drops-144869}, doi = {10.4230/LIPIcs.MFCS.2021.46}, annote = {Keywords: avoiding word, \v{C}ern\'{y} conjecture, rank conjecture, reset threshold, reset word, synchronizing automaton, synchronizing word} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov, and Marek Szykuła. Synchronizing Strongly Connected Partial DFAs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 12:1-12:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{berlinkov_et_al:LIPIcs.STACS.2021.12, author = {Berlinkov, Mikhail V. and Ferens, Robert and Ryzhikov, Andrew and Szyku{\l}a, Marek}, title = {{Synchronizing Strongly Connected Partial DFAs}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {12:1--12:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.12}, URN = {urn:nbn:de:0030-drops-136579}, doi = {10.4230/LIPIcs.STACS.2021.12}, annote = {Keywords: \v{C}ern\'{y} conjecture, literal automaton, partial automaton, prefix code, rank conjecture, reset threshold, reset word, synchronizing automaton, synchronizing word} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Paweł Gawrychowski, Martin Lange, Narad Rampersad, Jeffrey Shallit, and Marek Szykuła. Existential Length Universality. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 16:1-16:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{gawrychowski_et_al:LIPIcs.STACS.2020.16, author = {Gawrychowski, Pawe{\l} and Lange, Martin and Rampersad, Narad and Shallit, Jeffrey and Szyku{\l}a, Marek}, title = {{Existential Length Universality}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {16:1--16:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.16}, URN = {urn:nbn:de:0030-drops-118770}, doi = {10.4230/LIPIcs.STACS.2020.16}, annote = {Keywords: decision problem, deterministic automaton, nondeterministic automaton, pushdown automaton, regular expression, regular language, universality} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Henning Fernau, Vladimir V. Gusev, Stefan Hoffmann, Markus Holzer, Mikhail V. Volkov, and Petra Wolf. Computational Complexity of Synchronization under Regular Constraints. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fernau_et_al:LIPIcs.MFCS.2019.63, author = {Fernau, Henning and Gusev, Vladimir V. and Hoffmann, Stefan and Holzer, Markus and Volkov, Mikhail V. and Wolf, Petra}, title = {{Computational Complexity of Synchronization under Regular Constraints}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {63:1--63: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.63}, URN = {urn:nbn:de:0030-drops-110078}, doi = {10.4230/LIPIcs.MFCS.2019.63}, annote = {Keywords: Finite automata, synchronization, computational complexity} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Andrew Ryzhikov and Marek Szykula. Finding Short Synchronizing Words for Prefix Codes. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 21:1-21:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{ryzhikov_et_al:LIPIcs.MFCS.2018.21, author = {Ryzhikov, Andrew and Szykula, Marek}, title = {{Finding Short Synchronizing Words for Prefix Codes}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {21:1--21:14}, 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.21}, URN = {urn:nbn:de:0030-drops-96037}, doi = {10.4230/LIPIcs.MFCS.2018.21}, annote = {Keywords: synchronizing word, mortal word, avoiding word, Huffman decoder, inapproximability} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Mikhail V. Berlinkov, Robert Ferens, and Marek Szykula. Complexity of Preimage Problems for Deterministic Finite Automata. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 32:1-32:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{berlinkov_et_al:LIPIcs.MFCS.2018.32, author = {Berlinkov, Mikhail V. and Ferens, Robert and Szykula, Marek}, title = {{Complexity of Preimage Problems for Deterministic Finite Automata}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {32:1--32:14}, 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.32}, URN = {urn:nbn:de:0030-drops-96149}, doi = {10.4230/LIPIcs.MFCS.2018.32}, annote = {Keywords: avoiding word, extending word, extensible subset, reset word, synchronizing automaton} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Marek Szykula. Improving the Upper Bound on the Length of the Shortest Reset Word. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 56:1-56:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{szykula:LIPIcs.STACS.2018.56, author = {Szykula, Marek}, title = {{Improving the Upper Bound on the Length of the Shortest Reset Word}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {56:1--56:13}, 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.56}, URN = {urn:nbn:de:0030-drops-85160}, doi = {10.4230/LIPIcs.STACS.2018.56}, annote = {Keywords: avoiding word, Cerny conjecture, reset length, reset threshold, reset word, synchronizing automaton, synchronizing word} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Michalina Dzyga, Robert Ferens, Vladimir V. Gusev, and Marek Szykula. Attainable Values of Reset Thresholds. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 40:1-40:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{dzyga_et_al:LIPIcs.MFCS.2017.40, author = {Dzyga, Michalina and Ferens, Robert and Gusev, Vladimir V. and Szykula, Marek}, title = {{Attainable Values of Reset Thresholds}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {40:1--40: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.40}, URN = {urn:nbn:de:0030-drops-81220}, doi = {10.4230/LIPIcs.MFCS.2017.40}, annote = {Keywords: Cerny conjecture, exponent, primitive digraph, reset word, synchronizing automaton} }
Feedback for Dagstuhl Publishing