Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Bruno P. Cavalar and Igor C. Oliveira. Constant-Depth Circuits vs. Monotone Circuits. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 29:1-29:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cavalar_et_al:LIPIcs.CCC.2023.29, author = {Cavalar, Bruno P. and Oliveira, Igor C.}, title = {{Constant-Depth Circuits vs. Monotone Circuits}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {29:1--29:37}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.29}, URN = {urn:nbn:de:0030-drops-182998}, doi = {10.4230/LIPIcs.CCC.2023.29}, annote = {Keywords: circuit complexity, monotone circuit complexity, bounded-depth circuis, constraint-satisfaction problems} }
Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)
Emile Hazard and Denis Kuperberg. Explorable Automata. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hazard_et_al:LIPIcs.CSL.2023.24, author = {Hazard, Emile and Kuperberg, Denis}, title = {{Explorable Automata}}, booktitle = {31st EACSL Annual Conference on Computer Science Logic (CSL 2023)}, pages = {24:1--24:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-264-8}, ISSN = {1868-8969}, year = {2023}, volume = {252}, editor = {Klin, Bartek and Pimentel, Elaine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.24}, URN = {urn:nbn:de:0030-drops-174852}, doi = {10.4230/LIPIcs.CSL.2023.24}, annote = {Keywords: Nondeterminism, automata, complexity} }
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-dev.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 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)
Emile Hazard and Denis Kuperberg. Cyclic Proofs for Transfinite Expressions. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hazard_et_al:LIPIcs.CSL.2022.23, author = {Hazard, Emile and Kuperberg, Denis}, title = {{Cyclic Proofs for Transfinite Expressions}}, booktitle = {30th EACSL Annual Conference on Computer Science Logic (CSL 2022)}, pages = {23:1--23: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.23}, URN = {urn:nbn:de:0030-drops-157433}, doi = {10.4230/LIPIcs.CSL.2022.23}, annote = {Keywords: transfinite expressions, transfinite automata, cyclic proofs} }
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-dev.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 195, 6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021)
Anupam Das. On the Logical Strength of Confluence and Normalisation for Cyclic Proofs. In 6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 195, pp. 29:1-29:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{das:LIPIcs.FSCD.2021.29, author = {Das, Anupam}, title = {{On the Logical Strength of Confluence and Normalisation for Cyclic Proofs}}, booktitle = {6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021)}, pages = {29:1--29:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-191-7}, ISSN = {1868-8969}, year = {2021}, volume = {195}, editor = {Kobayashi, Naoki}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2021.29}, URN = {urn:nbn:de:0030-drops-142678}, doi = {10.4230/LIPIcs.FSCD.2021.29}, annote = {Keywords: confluence, normalisation, system T, circular proofs, reverse mathematics, type structures} }
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-dev.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 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Denis Kuperberg and Jan Martens. Regular Resynchronizability of Origin Transducers Is Undecidable. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kuperberg_et_al:LIPIcs.MFCS.2020.58, author = {Kuperberg, Denis and Martens, Jan}, title = {{Regular Resynchronizability of Origin Transducers Is Undecidable}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {58:1--58:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.58}, URN = {urn:nbn:de:0030-drops-127255}, doi = {10.4230/LIPIcs.MFCS.2020.58}, annote = {Keywords: transducers, origin, resynchronisation, MSO, one-way, two-way, undecidability} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Denis Kuperberg, Laureline Pinault, and Damien Pous. Cyclic Proofs and Jumping Automata. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kuperberg_et_al:LIPIcs.FSTTCS.2019.45, author = {Kuperberg, Denis and Pinault, Laureline and Pous, Damien}, title = {{Cyclic Proofs and Jumping Automata}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {45:1--45:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.45}, URN = {urn:nbn:de:0030-drops-116071}, doi = {10.4230/LIPIcs.FSTTCS.2019.45}, annote = {Keywords: Cyclic proofs, regular languages, multi-head automata, transducers} }
Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Marc Bagnol and Denis Kuperberg. Büchi Good-for-Games Automata Are Efficiently Recognizable. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bagnol_et_al:LIPIcs.FSTTCS.2018.16, author = {Bagnol, Marc and Kuperberg, Denis}, title = {{B\"{u}chi Good-for-Games Automata Are Efficiently Recognizable}}, booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)}, pages = {16:1--16:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-093-4}, ISSN = {1868-8969}, year = {2018}, volume = {122}, editor = {Ganguly, Sumit and Pandya, Paritosh}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.16}, URN = {urn:nbn:de:0030-drops-99157}, doi = {10.4230/LIPIcs.FSTTCS.2018.16}, annote = {Keywords: B\"{u}chi, automata, games, polynomial time, nondeterminism} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Denis Kuperberg and Anirban Majumdar. Width of Non-deterministic Automata. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{kuperberg_et_al:LIPIcs.STACS.2018.47, author = {Kuperberg, Denis and Majumdar, Anirban}, title = {{Width of Non-deterministic Automata}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {47:1--47: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.47}, URN = {urn:nbn:de:0030-drops-84963}, doi = {10.4230/LIPIcs.STACS.2018.47}, annote = {Keywords: width, non-deterministic automata, determinisation, good-for-games, complexity} }
Published in: LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016)
Javier Esparza, Denis Kuperberg, Anca Muscholl, and Igor Walukiewicz. Soundness in Negotiations. In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 12:1-12:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{esparza_et_al:LIPIcs.CONCUR.2016.12, author = {Esparza, Javier and Kuperberg, Denis and Muscholl, Anca and Walukiewicz, Igor}, title = {{Soundness in Negotiations}}, booktitle = {27th International Conference on Concurrency Theory (CONCUR 2016)}, pages = {12:1--12:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-017-0}, ISSN = {1868-8969}, year = {2016}, volume = {59}, editor = {Desharnais, Jos\'{e}e and Jagadeesan, Radha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.12}, URN = {urn:nbn:de:0030-drops-61636}, doi = {10.4230/LIPIcs.CONCUR.2016.12}, annote = {Keywords: Negotiations, workflows, soundness, verification, concurrency} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Thomas Colcombet, Denis Kuperberg, Amaldev Manuel, and Szymon Torunczyk. Cost Functions Definable by Min/Max Automata. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{colcombet_et_al:LIPIcs.STACS.2016.29, author = {Colcombet, Thomas and Kuperberg, Denis and Manuel, Amaldev and Torunczyk, Szymon}, title = {{Cost Functions Definable by Min/Max Automata}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {29:1--29:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.29}, URN = {urn:nbn:de:0030-drops-57305}, doi = {10.4230/LIPIcs.STACS.2016.29}, annote = {Keywords: distance automata, B-automata, regular cost functions, stabilisation monoids, decidability, min-automata, max-automata} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Laure Daviaud, Denis Kuperberg, and Jean-Éric Pin. Varieties of Cost Functions. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{daviaud_et_al:LIPIcs.STACS.2016.30, author = {Daviaud, Laure and Kuperberg, Denis and Pin, Jean-\'{E}ric}, title = {{Varieties of Cost Functions}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {30:1--30:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.30}, URN = {urn:nbn:de:0030-drops-57319}, doi = {10.4230/LIPIcs.STACS.2016.30}, annote = {Keywords: Cost functions, regular language, varieties, syntactic algebra} }
Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Shaull Almagor, Denis Kuperberg, and Orna Kupferman. The Sensing Cost of Monitoring and Synthesis. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 380-393, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{almagor_et_al:LIPIcs.FSTTCS.2015.380, author = {Almagor, Shaull and Kuperberg, Denis and Kupferman, Orna}, title = {{The Sensing Cost of Monitoring and Synthesis}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {380--393}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.380}, URN = {urn:nbn:de:0030-drops-56563}, doi = {10.4230/LIPIcs.FSTTCS.2015.380}, annote = {Keywords: Automata, regular languages, omega-regular languages, complexity, sensing, minimization} }
Feedback for Dagstuhl Publishing