Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Patricia Bouyer, Nathanaël Fijalkow, Mickael Randour, and Pierre Vandenhove. How to Play Optimally for Regular Objectives?. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 118:1-118:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bouyer_et_al:LIPIcs.ICALP.2023.118, author = {Bouyer, Patricia and Fijalkow, Nathana\"{e}l and Randour, Mickael and Vandenhove, Pierre}, title = {{How to Play Optimally for Regular Objectives?}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {118:1--118:18}, 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.118}, URN = {urn:nbn:de:0030-drops-181700}, doi = {10.4230/LIPIcs.ICALP.2023.118}, annote = {Keywords: two-player games on graphs, strategy complexity, regular languages, finite-memory strategies, NP-completeness} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Antonio Casares and Pierre Ohlmann. Characterising Memory in Infinite Games. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 122:1-122:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{casares_et_al:LIPIcs.ICALP.2023.122, author = {Casares, Antonio and Ohlmann, Pierre}, title = {{Characterising Memory in Infinite Games}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {122:1--122:18}, 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.122}, URN = {urn:nbn:de:0030-drops-181740}, doi = {10.4230/LIPIcs.ICALP.2023.122}, annote = {Keywords: Infinite duration games, Memory, Universal graphs} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
K. S. Thejaswini, Pierre Ohlmann, and Marcin Jurdziński. A Technique to Speed up Symmetric Attractor-Based Algorithms for Parity Games. 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. 44:1-44:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{thejaswini_et_al:LIPIcs.FSTTCS.2022.44, author = {Thejaswini, K. S. and Ohlmann, Pierre and Jurdzi\'{n}ski, Marcin}, title = {{A Technique to Speed up Symmetric Attractor-Based Algorithms for Parity Games}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {44:1--44: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.44}, URN = {urn:nbn:de:0030-drops-174365}, doi = {10.4230/LIPIcs.FSTTCS.2022.44}, annote = {Keywords: Parity games, Attractor decomposition, Quasipolynomial Algorithms, Universal trees} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Zhuan Khye Koh and Georg Loho. Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 63:1-63:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{koh_et_al:LIPIcs.MFCS.2022.63, author = {Koh, Zhuan Khye and Loho, Georg}, title = {{Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {63:1--63:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.63}, URN = {urn:nbn:de:0030-drops-168619}, doi = {10.4230/LIPIcs.MFCS.2022.63}, annote = {Keywords: parity games, strategy iteration, value iteration, progress measure, universal trees} }
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 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)
Guillermo A. Pérez and Ritam Raha. Revisiting Parameter Synthesis for One-Counter Automata. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 33:1-33:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{perez_et_al:LIPIcs.CSL.2022.33, author = {P\'{e}rez, Guillermo A. and Raha, Ritam}, title = {{Revisiting Parameter Synthesis for One-Counter Automata}}, booktitle = {30th EACSL Annual Conference on Computer Science Logic (CSL 2022)}, pages = {33:1--33:18}, 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.33}, URN = {urn:nbn:de:0030-drops-157534}, doi = {10.4230/LIPIcs.CSL.2022.33}, annote = {Keywords: Parametric one-counter automata, Reachability, Software Verification} }
Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Théo Matricon, Marie Anastacio, Nathanaël Fijalkow, Laurent Simon, and Holger H. Hoos. Statistical Comparison of Algorithm Performance Through Instance Selection. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 43:1-43:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{matricon_et_al:LIPIcs.CP.2021.43, author = {Matricon, Th\'{e}o and Anastacio, Marie and Fijalkow, Nathana\"{e}l and Simon, Laurent and Hoos, Holger H.}, title = {{Statistical Comparison of Algorithm Performance Through Instance Selection}}, booktitle = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)}, pages = {43:1--43:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-211-2}, ISSN = {1868-8969}, year = {2021}, volume = {210}, editor = {Michel, Laurent D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.43}, URN = {urn:nbn:de:0030-drops-153346}, doi = {10.4230/LIPIcs.CP.2021.43}, annote = {Keywords: Performance assessment, early stopping, automated reasoning solvers} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Antonio Casares, Thomas Colcombet, and Nathanaël Fijalkow. Optimal Transformations of Games and Automata Using Muller Conditions. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 123:1-123:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{casares_et_al:LIPIcs.ICALP.2021.123, author = {Casares, Antonio and Colcombet, Thomas and Fijalkow, Nathana\"{e}l}, title = {{Optimal Transformations of Games and Automata Using Muller Conditions}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {123:1--123:14}, 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.123}, URN = {urn:nbn:de:0030-drops-141928}, doi = {10.4230/LIPIcs.ICALP.2021.123}, annote = {Keywords: Automata over infinite words, Omega regular languages, Determinisation of automata} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Nathanaël Fijalkow, Paweł Gawrychowski, and Pierre Ohlmann. Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 34:1-34:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{fijalkow_et_al:LIPIcs.MFCS.2020.34, author = {Fijalkow, Nathana\"{e}l and Gawrychowski, Pawe{\l} and Ohlmann, Pierre}, title = {{Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {34:1--34:15}, 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.34}, URN = {urn:nbn:de:0030-drops-127011}, doi = {10.4230/LIPIcs.MFCS.2020.34}, annote = {Keywords: Mean payoff games, Universal graphs, Value iteration} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann, and Olivier Serre. Lower Bounds for Arithmetic Circuits via the Hankel Matrix. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 24:1-24:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{fijalkow_et_al:LIPIcs.STACS.2020.24, author = {Fijalkow, Nathana\"{e}l and Lagarde, Guillaume and Ohlmann, Pierre and Serre, Olivier}, title = {{Lower Bounds for Arithmetic Circuits via the Hankel Matrix}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {24:1--24:16}, 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.24}, URN = {urn:nbn:de:0030-drops-118859}, doi = {10.4230/LIPIcs.STACS.2020.24}, annote = {Keywords: Arithmetic Circuit Complexity, Lower Bounds, Parse Trees, Hankel Matrix} }
Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote, and Filip Mazowiecki. A Robust Class of Linear Recurrence Sequences. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 9:1-9:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{barloy_et_al:LIPIcs.CSL.2020.9, author = {Barloy, Corentin and Fijalkow, Nathana\"{e}l and Lhote, Nathan and Mazowiecki, Filip}, title = {{A Robust Class of Linear Recurrence Sequences}}, booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)}, pages = {9:1--9:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-132-0}, ISSN = {1868-8969}, year = {2020}, volume = {152}, editor = {Fern\'{a}ndez, Maribel 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.CSL.2020.9}, URN = {urn:nbn:de:0030-drops-116521}, doi = {10.4230/LIPIcs.CSL.2020.9}, annote = {Keywords: linear recurrence sequences, weighted automata, cost-register automata} }
Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Nathanaël Fijalkow, Bastien Maubert, Aniello Murano, and Sasha Rubin. Quantifying Bounds in Strategy Logic. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 23:1-23:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{fijalkow_et_al:LIPIcs.CSL.2018.23, author = {Fijalkow, Nathana\"{e}l and Maubert, Bastien and Murano, Aniello and Rubin, Sasha}, title = {{Quantifying Bounds in Strategy Logic}}, booktitle = {27th EACSL Annual Conference on Computer Science Logic (CSL 2018)}, pages = {23:1--23:23}, 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.23}, URN = {urn:nbn:de:0030-drops-96901}, doi = {10.4230/LIPIcs.CSL.2018.23}, annote = {Keywords: Prompt LTL, Strategy Logic, Model checking, Automata with counters} }
Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)
Nathanaël Fijalkow, Cristian Riveros, and James Worrell. Probabilistic Automata of Bounded Ambiguity. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 19:1-19:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{fijalkow_et_al:LIPIcs.CONCUR.2017.19, author = {Fijalkow, Nathana\"{e}l and Riveros, Cristian and Worrell, James}, title = {{Probabilistic Automata of Bounded Ambiguity}}, booktitle = {28th International Conference on Concurrency Theory (CONCUR 2017)}, pages = {19:1--19:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-048-4}, ISSN = {1868-8969}, year = {2017}, volume = {85}, editor = {Meyer, Roland and Nestmann, Uwe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.19}, URN = {urn:nbn:de:0030-drops-77716}, doi = {10.4230/LIPIcs.CONCUR.2017.19}, annote = {Keywords: Probabilistic Automata, Emptiness Problem, Stochastic Path Problem, Multi-Objective Optimisation Problems} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Nathanaël Fijalkow, Bartek Klin, and Prakash Panangaden. Expressiveness of Probabilistic Modal Logics, Revisited. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 105:1-105:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{fijalkow_et_al:LIPIcs.ICALP.2017.105, author = {Fijalkow, Nathana\"{e}l and Klin, Bartek and Panangaden, Prakash}, title = {{Expressiveness of Probabilistic Modal Logics, Revisited}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {105:1--105:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian 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.ICALP.2017.105}, URN = {urn:nbn:de:0030-drops-73683}, doi = {10.4230/LIPIcs.ICALP.2017.105}, annote = {Keywords: probabilistic modal logic, probabilistic bisimulation, probabilistic simulation} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Nathanaël Fijalkow, Pierre Ohlmann, Joël Ouaknine, Amaury Pouly, and James Worrell. Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 29:1-29:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{fijalkow_et_al:LIPIcs.STACS.2017.29, author = {Fijalkow, Nathana\"{e}l and Ohlmann, Pierre and Ouaknine, Jo\"{e}l and Pouly, Amaury and Worrell, James}, title = {{Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {29:1--29:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert 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.2017.29}, URN = {urn:nbn:de:0030-drops-70059}, doi = {10.4230/LIPIcs.STACS.2017.29}, annote = {Keywords: Verification,algebraic computation,Skolem Problem,Orbit Problem,invariants} }
Feedback for Dagstuhl Publishing