Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann, Markus Holzer, Ismaël Jecker, Mateus de Oliveira Oliveira, and Petra Wolf. On the Complexity of Intersection Non-emptiness for Star-Free Language Classes. 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. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{arrighi_et_al:LIPIcs.FSTTCS.2021.34, author = {Arrighi, Emmanuel and Fernau, Henning and Hoffmann, Stefan and Holzer, Markus and Jecker, Isma\"{e}l and de Oliveira Oliveira, Mateus and Wolf, Petra}, title = {{On the Complexity of Intersection Non-emptiness for Star-Free Language Classes}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {34:1--34:15}, 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.34}, URN = {urn:nbn:de:0030-drops-155456}, doi = {10.4230/LIPIcs.FSTTCS.2021.34}, annote = {Keywords: Intersection Non-emptiness Problem, Star-Free Languages, Straubing-Th\'{e}rien Hierarchy, dot-depth Hierarchy, Commutative Languages, Complexity} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Hermann Gruber and Markus Holzer. Optimal Regular Expressions for Palindromes of Given Length. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{gruber_et_al:LIPIcs.MFCS.2021.52, author = {Gruber, Hermann and Holzer, Markus}, title = {{Optimal Regular Expressions for Palindromes of Given Length}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {52:1--52:15}, 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.52}, URN = {urn:nbn:de:0030-drops-144921}, doi = {10.4230/LIPIcs.MFCS.2021.52}, annote = {Keywords: regular expression, descriptional complexity, lower bound, upper bound, recurrence, sum of digits} }
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 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Markus Holzer and Jan-Tobias Maurer. Selection Via the Bogo-Method - More on the Analysis of Perversely Awful Randomized Algorithms. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{holzer_et_al:LIPIcs.FUN.2018.23, author = {Holzer, Markus and Maurer, Jan-Tobias}, title = {{Selection Via the Bogo-Method - More on the Analysis of Perversely Awful Randomized Algorithms}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {23:1--23:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-067-5}, ISSN = {1868-8969}, year = {2018}, volume = {100}, editor = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.23}, URN = {urn:nbn:de:0030-drops-88146}, doi = {10.4230/LIPIcs.FUN.2018.23}, annote = {Keywords: selection, bogo-method, combinatorial sums and series, inverse binomial coefficients, experimental result} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Felix Brandt, Felix Fischer, and Markus Holzer. On Iterated Dominance, Matrix Elimination, and Matched Paths. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 107-118, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{brandt_et_al:LIPIcs.STACS.2010.2448, author = {Brandt, Felix and Fischer, Felix and Holzer, Markus}, title = {{On Iterated Dominance, Matrix Elimination, and Matched Paths}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {107--118}, 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.2448}, URN = {urn:nbn:de:0030-drops-24485}, doi = {10.4230/LIPIcs.STACS.2010.2448}, annote = {Keywords: Algorithmic Game Theory, Computational Complexity, Iterated Dominance, Matching} }