Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Amina Doumane, Samuel Humeau, and Damien Pous. A Finite Presentation of Graphs of Treewidth at Most Three. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 135:1-135:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{doumane_et_al:LIPIcs.ICALP.2024.135, author = {Doumane, Amina and Humeau, Samuel and Pous, Damien}, title = {{A Finite Presentation of Graphs of Treewidth at Most Three}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {135:1--135:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.135}, URN = {urn:nbn:de:0030-drops-202787}, doi = {10.4230/LIPIcs.ICALP.2024.135}, annote = {Keywords: Graphs, treewidth, connectedness, axiomatisation, series-parallel expressions} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Paul Gallot, Sebastian Maneth, Keisuke Nakano, and Charles Peyrat. Deciding Linear Height and Linear Size-To-Height Increase of Macro Tree Transducers. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 138:1-138:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gallot_et_al:LIPIcs.ICALP.2024.138, author = {Gallot, Paul and Maneth, Sebastian and Nakano, Keisuke and Peyrat, Charles}, title = {{Deciding Linear Height and Linear Size-To-Height Increase of Macro Tree Transducers}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {138:1--138:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.138}, URN = {urn:nbn:de:0030-drops-202818}, doi = {10.4230/LIPIcs.ICALP.2024.138}, annote = {Keywords: automata, formal language theory, macro tree transducer, normal form} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Cheng Zhang, Arthur Azevedo de Amorim, and Marco Gaboardi. Domain Reasoning in TopKAT. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 157:1-157:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{zhang_et_al:LIPIcs.ICALP.2024.157, author = {Zhang, Cheng and de Amorim, Arthur Azevedo and Gaboardi, Marco}, title = {{Domain Reasoning in TopKAT}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {157:1--157:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.157}, URN = {urn:nbn:de:0030-drops-203003}, doi = {10.4230/LIPIcs.ICALP.2024.157}, annote = {Keywords: Kleene algebra, Kleene Algebra With Tests, Kleene Algebra With Domain, Kleene Algebra With Top and Tests, Completeness, Decidability} }
Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Vincent Moreau and Lê Thành Dũng (Tito) Nguyễn. Syntactically and Semantically Regular Languages of λ-Terms Coincide Through Logical Relations. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 40:1-40:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{moreau_et_al:LIPIcs.CSL.2024.40, author = {Moreau, Vincent and Nguy\~{ê}n, L\^{e} Th\`{a}nh D\~{u}ng (Tito)}, title = {{Syntactically and Semantically Regular Languages of \lambda-Terms Coincide Through Logical Relations}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {40:1--40:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-310-2}, ISSN = {1868-8969}, year = {2024}, volume = {288}, editor = {Murano, Aniello 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.CSL.2024.40}, URN = {urn:nbn:de:0030-drops-196831}, doi = {10.4230/LIPIcs.CSL.2024.40}, annote = {Keywords: regular languages, simple types, denotational semantics, logical relations} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Abhishek De, Farzad Jafarrahmani, and Alexis Saurin. Phase Semantics for Linear Logic with Least and Greatest Fixed Points. 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. 35:1-35:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{de_et_al:LIPIcs.FSTTCS.2022.35, author = {De, Abhishek and Jafarrahmani, Farzad and Saurin, Alexis}, title = {{Phase Semantics for Linear Logic with Least and Greatest Fixed Points}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {35:1--35:23}, 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.35}, URN = {urn:nbn:de:0030-drops-174272}, doi = {10.4230/LIPIcs.FSTTCS.2022.35}, annote = {Keywords: Linear logic, fixed points, phase semantics, closure ordinals, cut elimination} }
Published in: LIPIcs, Volume 243, 33rd International Conference on Concurrency Theory (CONCUR 2022)
Damien Pous and Jana Wagemaker. Completeness Theorems for Kleene Algebra with Top. In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{pous_et_al:LIPIcs.CONCUR.2022.26, author = {Pous, Damien and Wagemaker, Jana}, title = {{Completeness Theorems for Kleene Algebra with Top}}, booktitle = {33rd International Conference on Concurrency Theory (CONCUR 2022)}, pages = {26:1--26:18}, 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.26}, URN = {urn:nbn:de:0030-drops-170890}, doi = {10.4230/LIPIcs.CONCUR.2022.26}, annote = {Keywords: Kleene algebra, Hypotheses, Completeness, Closed languages} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Amina Doumane. Regular Expressions for Tree-Width 2 Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 121:1-121:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{doumane:LIPIcs.ICALP.2022.121, author = {Doumane, Amina}, title = {{Regular Expressions for Tree-Width 2 Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {121:1--121: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.121}, URN = {urn:nbn:de:0030-drops-164627}, doi = {10.4230/LIPIcs.ICALP.2022.121}, annote = {Keywords: Tree width, MSO, Regular expressions} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Amina Doumane. Non-Axiomatizability of the Equational Theories of Positive Relation Algebras (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{doumane:LIPIcs.MFCS.2021.1, author = {Doumane, Amina}, title = {{Non-Axiomatizability of the Equational Theories of Positive Relation Algebras}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {1:1--1:1}, 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.1}, URN = {urn:nbn:de:0030-drops-144417}, doi = {10.4230/LIPIcs.MFCS.2021.1}, annote = {Keywords: Relation algebra, Graph homomorphism, Equational theories, First-order logic} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Amina Doumane. Graph Characterization of the Universal Theory of Relations. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{doumane:LIPIcs.MFCS.2021.41, author = {Doumane, Amina}, title = {{Graph Characterization of the Universal Theory of Relations}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {41:1--41: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.41}, URN = {urn:nbn:de:0030-drops-144815}, doi = {10.4230/LIPIcs.MFCS.2021.41}, annote = {Keywords: Relation algebra, Graph homomorphism, Equational theories, First-order logic} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Lê Thành Dũng (Tito) Nguyễn, Camille Noûs, and Pierre Pradic. Comparison-Free Polyregular Functions. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 139:1-139:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{nguyen_et_al:LIPIcs.ICALP.2021.139, author = {Nguy\~{ê}n, L\^{e} Th\`{a}nh D\~{u}ng (Tito) and No\^{u}s, Camille and Pradic, Pierre}, title = {{Comparison-Free Polyregular Functions}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {139:1--139:20}, 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.139}, URN = {urn:nbn:de:0030-drops-142087}, doi = {10.4230/LIPIcs.ICALP.2021.139}, annote = {Keywords: pebble transducers, HDT0L systems, polyregular functions} }
Published in: LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020)
Amina Doumane and Damien Pous. Non Axiomatisability of Positive Relation Algebras with Constants, via Graph Homomorphisms. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{doumane_et_al:LIPIcs.CONCUR.2020.29, author = {Doumane, Amina and Pous, Damien}, title = {{Non Axiomatisability of Positive Relation Algebras with Constants, via Graph Homomorphisms}}, booktitle = {31st International Conference on Concurrency Theory (CONCUR 2020)}, pages = {29:1--29:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-160-3}, ISSN = {1868-8969}, year = {2020}, volume = {171}, editor = {Konnov, Igor and Kov\'{a}cs, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.29}, URN = {urn:nbn:de:0030-drops-128411}, doi = {10.4230/LIPIcs.CONCUR.2020.29}, annote = {Keywords: Relation algebra, graph homomorphisms, (in)equational theories} }
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 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Paul Brunet. A Complete Axiomatisation of a Fragment of Language Algebra. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{brunet:LIPIcs.CSL.2020.11, author = {Brunet, Paul}, title = {{A Complete Axiomatisation of a Fragment of Language Algebra}}, booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)}, pages = {11:1--11:15}, 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.11}, URN = {urn:nbn:de:0030-drops-116546}, doi = {10.4230/LIPIcs.CSL.2020.11}, annote = {Keywords: Kleene algebra, language algebra, completeness theorem, axiomatisation} }
Published in: LIPIcs, Volume 118, 29th International Conference on Concurrency Theory (CONCUR 2018)
Amina Doumane and Damien Pous. Completeness for Identity-free Kleene Lattices. In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{doumane_et_al:LIPIcs.CONCUR.2018.18, author = {Doumane, Amina and Pous, Damien}, title = {{Completeness for Identity-free Kleene Lattices}}, booktitle = {29th International Conference on Concurrency Theory (CONCUR 2018)}, pages = {18:1--18: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.18}, URN = {urn:nbn:de:0030-drops-95564}, doi = {10.4230/LIPIcs.CONCUR.2018.18}, annote = {Keywords: Kleene algebra, Graph languages, Petri Automata, Kleene theorem} }
Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)
David Baelde, Amina Doumane, and Alexis Saurin. Infinitary Proof Theory: the Multiplicative Additive Case. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{baelde_et_al:LIPIcs.CSL.2016.42, author = {Baelde, David and Doumane, Amina and Saurin, Alexis}, title = {{Infinitary Proof Theory: the Multiplicative Additive Case}}, booktitle = {25th EACSL Annual Conference on Computer Science Logic (CSL 2016)}, pages = {42:1--42:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-022-4}, ISSN = {1868-8969}, year = {2016}, volume = {62}, editor = {Talbot, Jean-Marc and Regnier, Laurent}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.42}, URN = {urn:nbn:de:0030-drops-65825}, doi = {10.4230/LIPIcs.CSL.2016.42}, annote = {Keywords: Infinitary proofs, linear logic} }
Feedback for Dagstuhl Publishing