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 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Lê Thành Dũng Nguyễn and Pierre Pradic. Implicit Automata in Typed λ-Calculi I: Aperiodicity in a Non-Commutative Logic. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 135:1-135:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{nguyen_et_al:LIPIcs.ICALP.2020.135, author = {Nguy\~{ê}n, L\^{e} Th\`{a}nh D\~{u}ng and Pradic, Pierre}, title = {{Implicit Automata in Typed \lambda-Calculi I: Aperiodicity in a Non-Commutative Logic}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {135:1--135:20}, 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.135}, URN = {urn:nbn:de:0030-drops-125426}, doi = {10.4230/LIPIcs.ICALP.2020.135}, annote = {Keywords: Church encodings, ordered linear types, star-free languages} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Marie Fortin. FO = FO^3 for Linear Orders with Monotone Binary Relations (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 116:1-116:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fortin:LIPIcs.ICALP.2019.116, author = {Fortin, Marie}, title = {{FO = FO^3 for Linear Orders with Monotone Binary Relations}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {116:1--116:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.116}, URN = {urn:nbn:de:0030-drops-106923}, doi = {10.4230/LIPIcs.ICALP.2019.116}, annote = {Keywords: first-order logic, three-variable property, propositional dynamic logic} }
Published in: LIPIcs, Volume 118, 29th International Conference on Concurrency Theory (CONCUR 2018)
Benedikt Bollig, Marie Fortin, and Paul Gastin. It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before". In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bollig_et_al:LIPIcs.CONCUR.2018.7, author = {Bollig, Benedikt and Fortin, Marie and Gastin, Paul}, title = {{It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before"}}, booktitle = {29th International Conference on Concurrency Theory (CONCUR 2018)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-087-3}, ISSN = {1868-8969}, year = {2018}, volume = {118}, editor = {Schewe, Sven and Zhang, Lijun}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2018.7}, URN = {urn:nbn:de:0030-drops-95455}, doi = {10.4230/LIPIcs.CONCUR.2018.7}, annote = {Keywords: communicating finite-state machines, first-order logic, happened-before relation} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Benedikt Bollig, Marie Fortin, and Paul Gastin. Communicating Finite-State Machines and Two-Variable Logic. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bollig_et_al:LIPIcs.STACS.2018.17, author = {Bollig, Benedikt and Fortin, Marie and Gastin, Paul}, title = {{Communicating Finite-State Machines and Two-Variable Logic}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {17:1--17:14}, 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.17}, URN = {urn:nbn:de:0030-drops-85298}, doi = {10.4230/LIPIcs.STACS.2018.17}, annote = {Keywords: communicating finite-state machines, MSO logic, message sequence charts} }
Feedback for Dagstuhl Publishing