Published in: LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023)
Stéphane Demri and Karin Quaas. Constraint Automata on Infinite Data Trees: from CTL(ℤ)/CTL^*(ℤ) to Decision Procedures. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{demri_et_al:LIPIcs.CONCUR.2023.29, author = {Demri, St\'{e}phane and Quaas, Karin}, title = {{Constraint Automata on Infinite Data Trees: from CTL(\mathbb{Z})/CTL^*(\mathbb{Z}) to Decision Procedures}}, booktitle = {34th International Conference on Concurrency Theory (CONCUR 2023)}, pages = {29:1--29:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.29}, URN = {urn:nbn:de:0030-drops-190238}, doi = {10.4230/LIPIcs.CONCUR.2023.29}, annote = {Keywords: Constraints, Constraint Automata, Temporal Logics, Infinite Data Trees} }
Published in: LIPIcs, Volume 269, 28th International Conference on Types for Proofs and Programs (TYPES 2022)
Catherine Dubois, Nicolas Magaud, and Alain Giorgetti. Pragmatic Isomorphism Proofs Between Coq Representations: Application to Lambda-Term Families. In 28th International Conference on Types for Proofs and Programs (TYPES 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 269, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dubois_et_al:LIPIcs.TYPES.2022.11, author = {Dubois, Catherine and Magaud, Nicolas and Giorgetti, Alain}, title = {{Pragmatic Isomorphism Proofs Between Coq Representations: Application to Lambda-Term Families}}, booktitle = {28th International Conference on Types for Proofs and Programs (TYPES 2022)}, pages = {11:1--11:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-285-3}, ISSN = {1868-8969}, year = {2023}, volume = {269}, editor = {Kesner, Delia and P\'{e}drot, Pierre-Marie}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TYPES.2022.11}, URN = {urn:nbn:de:0030-drops-184548}, doi = {10.4230/LIPIcs.TYPES.2022.11}, annote = {Keywords: Data Representations, Isomorphisms, dependent Types, formal Proofs, random Generation, lambda Terms, Coq} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, and Stéphan Thomassé. Twin-Width VIII: Delineation and Win-Wins. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bonnet_et_al:LIPIcs.IPEC.2022.9, author = {Bonnet, \'{E}douard and Chakraborty, Dibyayan and Kim, Eun Jung and K\"{o}hler, Noleen and Lopes, Raul and Thomass\'{e}, St\'{e}phan}, title = {{Twin-Width VIII: Delineation and Win-Wins}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {9:1--9:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.9}, URN = {urn:nbn:de:0030-drops-173650}, doi = {10.4230/LIPIcs.IPEC.2022.9}, annote = {Keywords: Twin-width, intersection graphs, visibility graphs, monadic dependence and stability, first-order model checking} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Han Jiang, Shang-En Huang, Thatchaphol Saranurak, and Tian Zhang. Vertex Sparsifiers for Hyperedge Connectivity. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{jiang_et_al:LIPIcs.ESA.2022.70, author = {Jiang, Han and Huang, Shang-En and Saranurak, Thatchaphol and Zhang, Tian}, title = {{Vertex Sparsifiers for Hyperedge Connectivity}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {70:1--70:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.70}, URN = {urn:nbn:de:0030-drops-170081}, doi = {10.4230/LIPIcs.ESA.2022.70}, annote = {Keywords: Vertex sparsifier, hypergraph, connectivity} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Dmitry Itsykson and Artur Riazanov. Automating OBDD proofs is NP-hard. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{itsykson_et_al:LIPIcs.MFCS.2022.59, author = {Itsykson, Dmitry and Riazanov, Artur}, title = {{Automating OBDD proofs is NP-hard}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {59:1--59: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.59}, URN = {urn:nbn:de:0030-drops-168575}, doi = {10.4230/LIPIcs.MFCS.2022.59}, annote = {Keywords: proof complexity, OBDD, automatability, lifting, dag-like communication} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Dmitry Sokolov. Pseudorandom Generators, Resolution and Heavy Width. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{sokolov:LIPIcs.CCC.2022.15, author = {Sokolov, Dmitry}, title = {{Pseudorandom Generators, Resolution and Heavy Width}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {15:1--15:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.15}, URN = {urn:nbn:de:0030-drops-165770}, doi = {10.4230/LIPIcs.CCC.2022.15}, annote = {Keywords: proof complexity, pseudorandom generators, resolution, lower bounds} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Stéphan Thomassé. A Brief Tour in Twin-Width (Invited Talk). In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 6:1-6:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{thomasse:LIPIcs.ICALP.2022.6, author = {Thomass\'{e}, St\'{e}phan}, title = {{A Brief Tour in Twin-Width}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {6:1--6:5}, 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.6}, URN = {urn:nbn:de:0030-drops-163473}, doi = {10.4230/LIPIcs.ICALP.2022.6}, annote = {Keywords: Twin-width, matrices, ordered graphs, enumerative combinatorics, model theory, algorithms, computational complexity, Ramsey theory} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz, and Mateusz Skomra. Universal Complexity Bounds Based on Value Iteration and Application to Entropy Games. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 110:1-110:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{allamigeon_et_al:LIPIcs.ICALP.2022.110, author = {Allamigeon, Xavier and Gaubert, St\'{e}phane and Katz, Ricardo D. and Skomra, Mateusz}, title = {{Universal Complexity Bounds Based on Value Iteration and Application to Entropy Games}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {110:1--110: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.110}, URN = {urn:nbn:de:0030-drops-164511}, doi = {10.4230/LIPIcs.ICALP.2022.110}, annote = {Keywords: Mean-payoff games, entropy games, value iteration, Perron root, separation bounds, parameterized complexity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ville Salo and Ilkka Törmä. What Can Oracles Teach Us About the Ultimate Fate of Life?. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 131:1-131:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{salo_et_al:LIPIcs.ICALP.2022.131, author = {Salo, Ville and T\"{o}rm\"{a}, Ilkka}, title = {{What Can Oracles Teach Us About the Ultimate Fate of Life?}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {131:1--131: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.131}, URN = {urn:nbn:de:0030-drops-164721}, doi = {10.4230/LIPIcs.ICALP.2022.131}, annote = {Keywords: Game of Life, cellular automata, limit set, symbolic dynamics} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Julien Bourgeois, Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Benoît Piranda, Christian Rieck, and Christian Scheffer. Space Ants: Episode II - Coordinating Connected Catoms (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 65:1-65:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bourgeois_et_al:LIPIcs.SoCG.2022.65, author = {Bourgeois, Julien and Fekete, S\'{a}ndor P. and Kosfeld, Ramin and Kramer, Peter and Piranda, Beno\^{i}t and Rieck, Christian and Scheffer, Christian}, title = {{Space Ants: Episode II - Coordinating Connected Catoms}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {65:1--65:6}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.65}, URN = {urn:nbn:de:0030-drops-160732}, doi = {10.4230/LIPIcs.SoCG.2022.65}, annote = {Keywords: Motion planning, parallel motion, bounded stretch, scaled shape, makespan, connectivity, swarm robotics} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Ahmad Biniaz, Majid Daliri, and Amir Hossein Moradpour. A 10-Approximation of the π/2-MST. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{biniaz_et_al:LIPIcs.STACS.2022.13, author = {Biniaz, Ahmad and Daliri, Majid and Moradpour, Amir Hossein}, title = {{A 10-Approximation of the \pi/2-MST}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {13:1--13:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.13}, URN = {urn:nbn:de:0030-drops-158232}, doi = {10.4230/LIPIcs.STACS.2022.13}, annote = {Keywords: Euclidean spanning trees, approximation algorithms, bounded-angle visibility} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Noah Fleming, Mika Göös, Stefan Grosser, and Robert Robere. On Semi-Algebraic Proofs and Algorithms. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 69:1-69:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fleming_et_al:LIPIcs.ITCS.2022.69, author = {Fleming, Noah and G\"{o}\"{o}s, Mika and Grosser, Stefan and Robere, Robert}, title = {{On Semi-Algebraic Proofs and Algorithms}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {69:1--69:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.69}, URN = {urn:nbn:de:0030-drops-156658}, doi = {10.4230/LIPIcs.ITCS.2022.69}, annote = {Keywords: Proof Complexity, Extended Formulations, Circuit Complexity, Sherali-Adams} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant. Twin-Width and Polynomial Kernels. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bonnet_et_al:LIPIcs.IPEC.2021.10, author = {Bonnet, \'{E}douard and Kim, Eun Jung and Reinald, Amadeus and Thomass\'{e}, St\'{e}phan and Watrigant, R\'{e}mi}, title = {{Twin-Width and Polynomial Kernels}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.10}, URN = {urn:nbn:de:0030-drops-153932}, doi = {10.4230/LIPIcs.IPEC.2021.10}, annote = {Keywords: Twin-width, kernelization, lower bounds, Dominating Set} }
Published in: OASIcs, Volume 93, 3rd Conference on Language, Data and Knowledge (LDK 2021)
Massinissa Atmani and Mathieu Lafourcade. Universal Dependencies for Multilingual Open Information Extraction. In 3rd Conference on Language, Data and Knowledge (LDK 2021). Open Access Series in Informatics (OASIcs), Volume 93, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{atmani_et_al:OASIcs.LDK.2021.24, author = {Atmani, Massinissa and Lafourcade, Mathieu}, title = {{Universal Dependencies for Multilingual Open Information Extraction}}, booktitle = {3rd Conference on Language, Data and Knowledge (LDK 2021)}, pages = {24:1--24:15}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-199-3}, ISSN = {2190-6807}, year = {2021}, volume = {93}, editor = {Gromann, Dagmar and S\'{e}rasset, Gilles and Declerck, Thierry and McCrae, John P. and Gracia, Jorge and Bosque-Gil, Julia and Bobillo, Fernando and Heinisch, Barbara}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.LDK.2021.24}, URN = {urn:nbn:de:0030-drops-145600}, doi = {10.4230/OASIcs.LDK.2021.24}, annote = {Keywords: Natural Language Processing, Information Extraction, Machine Learning} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Yaroslav Alekseev. A Lower Bound for Polynomial Calculus with Extension Rule. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{alekseev:LIPIcs.CCC.2021.21, author = {Alekseev, Yaroslav}, title = {{A Lower Bound for Polynomial Calculus with Extension Rule}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {21:1--21:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.21}, URN = {urn:nbn:de:0030-drops-142959}, doi = {10.4230/LIPIcs.CCC.2021.21}, annote = {Keywords: proof complexity, algebraic proofs, polynomial calculus} }
Feedback for Dagstuhl Publishing