Published in: LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023)
Enzo Erlich, Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, and Martin Zimmermann. History-Deterministic Parikh Automata. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 31:1-31:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{erlich_et_al:LIPIcs.CONCUR.2023.31, author = {Erlich, Enzo and Guha, Shibashis and Jecker, Isma\"{e}l and Lehtinen, Karoliina and Zimmermann, Martin}, title = {{History-Deterministic Parikh Automata}}, booktitle = {34th International Conference on Concurrency Theory (CONCUR 2023)}, pages = {31:1--31:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-299-0}, ISSN = {1868-8969}, year = {2023}, volume = {279}, editor = {P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.31}, URN = {urn:nbn:de:0030-drops-190250}, doi = {10.4230/LIPIcs.CONCUR.2023.31}, annote = {Keywords: Parikh automata, History-determinism, Reversal-bounded Counter Machines} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Karoliina Lehtinen. A Brief History of History-Determinism (Invited Talk). In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 1:1-1:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{lehtinen:LIPIcs.STACS.2023.1, author = {Lehtinen, Karoliina}, title = {{A Brief History of History-Determinism}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {1:1--1:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.1}, URN = {urn:nbn:de:0030-drops-176535}, doi = {10.4230/LIPIcs.STACS.2023.1}, annote = {Keywords: History-determinism, nondeterminism, automata, good-for-games} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, and Martin Zimmermann. Parikh Automata over Infinite Words. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 40:1-40:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{guha_et_al:LIPIcs.FSTTCS.2022.40, author = {Guha, Shibashis and Jecker, Isma\"{e}l and Lehtinen, Karoliina and Zimmermann, Martin}, title = {{Parikh Automata over Infinite Words}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {40:1--40:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.40}, URN = {urn:nbn:de:0030-drops-174327}, doi = {10.4230/LIPIcs.FSTTCS.2022.40}, annote = {Keywords: Parikh automata, \omega-automata, Infinite Games} }
Published in: LIPIcs, Volume 243, 33rd International Conference on Concurrency Theory (CONCUR 2022)
Thomas A. Henzinger, Karoliina Lehtinen, and Patrick Totzke. History-Deterministic Timed Automata. In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 14:1-14:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{henzinger_et_al:LIPIcs.CONCUR.2022.14, author = {Henzinger, Thomas A. and Lehtinen, Karoliina and Totzke, Patrick}, title = {{History-Deterministic Timed Automata}}, booktitle = {33rd International Conference on Concurrency Theory (CONCUR 2022)}, pages = {14:1--14:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-246-4}, ISSN = {1868-8969}, year = {2022}, volume = {243}, editor = {Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2022.14}, URN = {urn:nbn:de:0030-drops-170778}, doi = {10.4230/LIPIcs.CONCUR.2022.14}, annote = {Keywords: Timed Automata, History-determinism, Good-for-games, fair simulation, synthesis} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Antonio Casares, Thomas Colcombet, and Karoliina Lehtinen. On the Size of Good-For-Games Rabin Automata and Its Link with the Memory in Muller Games. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 117:1-117:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{casares_et_al:LIPIcs.ICALP.2022.117, author = {Casares, Antonio and Colcombet, Thomas and Lehtinen, Karoliina}, title = {{On the Size of Good-For-Games Rabin Automata and Its Link with the Memory in Muller Games}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {117:1--117:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.117}, URN = {urn:nbn:de:0030-drops-164580}, doi = {10.4230/LIPIcs.ICALP.2022.117}, annote = {Keywords: Infinite duration games, Muller games, Rabin conditions, omega-regular languages, memory in games, good-for-games automata} }
Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)
Udi Boker. Between Deterministic and Nondeterministic Quantitative Automata (Invited Talk). In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 1:1-1:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{boker:LIPIcs.CSL.2022.1, author = {Boker, Udi}, title = {{Between Deterministic and Nondeterministic Quantitative Automata}}, booktitle = {30th EACSL Annual Conference on Computer Science Logic (CSL 2022)}, pages = {1:1--1:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-218-1}, ISSN = {1868-8969}, year = {2022}, volume = {216}, editor = {Manea, Florin and Simpson, Alex}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.1}, URN = {urn:nbn:de:0030-drops-157218}, doi = {10.4230/LIPIcs.CSL.2022.1}, annote = {Keywords: Quantitative Automata, Measure of Nondeterminism, Determinism} }
Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)
Antonio Casares. On the Minimisation of Transition-Based Rabin Automata and the Chromatic Memory Requirements of Muller Conditions. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 12:1-12:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{casares:LIPIcs.CSL.2022.12, author = {Casares, Antonio}, title = {{On the Minimisation of Transition-Based Rabin Automata and the Chromatic Memory Requirements of Muller Conditions}}, booktitle = {30th EACSL Annual Conference on Computer Science Logic (CSL 2022)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-218-1}, ISSN = {1868-8969}, year = {2022}, volume = {216}, editor = {Manea, Florin and Simpson, Alex}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.12}, URN = {urn:nbn:de:0030-drops-157322}, doi = {10.4230/LIPIcs.CSL.2022.12}, annote = {Keywords: Automata on Infinite Words, Games on Graphs, Arena-Independent Memory, Complexity} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Udi Boker and Karoliina Lehtinen. History Determinism vs. Good for Gameness in Quantitative Automata. 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. 38:1-38:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{boker_et_al:LIPIcs.FSTTCS.2021.38, author = {Boker, Udi and Lehtinen, Karoliina}, title = {{History Determinism vs. Good for Gameness in Quantitative Automata}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {38:1--38:20}, 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.38}, URN = {urn:nbn:de:0030-drops-155495}, doi = {10.4230/LIPIcs.FSTTCS.2021.38}, annote = {Keywords: Good for games, history determinism, alternation, quantitative automata} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Marie Fortin, Louwe B. Kuijer, Patrick Totzke, and Martin Zimmermann. HyperLTL Satisfiability Is Σ₁¹-Complete, HyperCTL* Satisfiability Is Σ₁²-Complete. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 47:1-47:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{fortin_et_al:LIPIcs.MFCS.2021.47, author = {Fortin, Marie and Kuijer, Louwe B. and Totzke, Patrick and Zimmermann, Martin}, title = {{HyperLTL Satisfiability Is \Sigma₁¹-Complete, HyperCTL* Satisfiability Is \Sigma₁²-Complete}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {47:1--47:19}, 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.47}, URN = {urn:nbn:de:0030-drops-144870}, doi = {10.4230/LIPIcs.MFCS.2021.47}, annote = {Keywords: HyperLTL, HyperCTL*, Satisfiability, Analytical Hierarchy} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, and Martin Zimmermann. A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 53:1-53:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{guha_et_al:LIPIcs.MFCS.2021.53, author = {Guha, Shibashis and Jecker, Isma\"{e}l and Lehtinen, Karoliina and Zimmermann, Martin}, title = {{A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {53:1--53:20}, 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.53}, URN = {urn:nbn:de:0030-drops-144932}, doi = {10.4230/LIPIcs.MFCS.2021.53}, annote = {Keywords: Pushdown Automata, Good-for-games, Synthesis, Succintness} }
Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)
Luca Aceto, Antonis Achilleos, Adrian Francalanza, Anna Ingólfsdóttir, and Karoliina Lehtinen. The Best a Monitor Can Do. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 7:1-7:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{aceto_et_al:LIPIcs.CSL.2021.7, author = {Aceto, Luca and Achilleos, Antonis and Francalanza, Adrian and Ing\'{o}lfsd\'{o}ttir, Anna and Lehtinen, Karoliina}, title = {{The Best a Monitor Can Do}}, booktitle = {29th EACSL Annual Conference on Computer Science Logic (CSL 2021)}, pages = {7:1--7:23}, 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.7}, URN = {urn:nbn:de:0030-drops-134416}, doi = {10.4230/LIPIcs.CSL.2021.7}, annote = {Keywords: monitorability, branching-time logics, runtime verification} }
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 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Sven Schewe. Minimising Good-For-Games Automata Is NP-Complete. 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. 56:1-56:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{schewe:LIPIcs.FSTTCS.2020.56, author = {Schewe, Sven}, title = {{Minimising Good-For-Games Automata Is NP-Complete}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {56:1--56: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.56}, URN = {urn:nbn:de:0030-drops-132973}, doi = {10.4230/LIPIcs.FSTTCS.2020.56}, annote = {Keywords: Good-for-Games Automata, Automata Minimisation} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Paweł Parys. Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 10:1-10:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{parys:LIPIcs.MFCS.2019.10, author = {Parys, Pawe{\l}}, title = {{Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {10:1--10: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.10}, URN = {urn:nbn:de:0030-drops-109543}, doi = {10.4230/LIPIcs.MFCS.2019.10}, annote = {Keywords: Parity games, Zielonka’s algorithm, quasi-polynomial time} }
Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)
Laure Daviaud, Marcin Jurdziński, and Karoliina Lehtinen. Alternating Weak Automata from Universal Trees. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 18:1-18:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{daviaud_et_al:LIPIcs.CONCUR.2019.18, author = {Daviaud, Laure and Jurdzi\'{n}ski, Marcin and Lehtinen, Karoliina}, title = {{Alternating Weak Automata from Universal Trees}}, booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)}, pages = {18:1--18:14}, 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.18}, URN = {urn:nbn:de:0030-drops-109208}, doi = {10.4230/LIPIcs.CONCUR.2019.18}, annote = {Keywords: alternating automata, weak automata, B\"{u}chi automata, parity automata, parity games, universal trees} }
Feedback for Dagstuhl Publishing