LIPIcs, Volume 48
ICDT 2016, March 15-18, 2016, Bordeaux, France
Editors: Wim Martens and Thomas Zeume
Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)
Simon Prucker and Lutz Schröder. Nominal Tree Automata with Name Allocation. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{prucker_et_al:LIPIcs.CONCUR.2024.35, author = {Prucker, Simon and Schr\"{o}der, Lutz}, title = {{Nominal Tree Automata with Name Allocation}}, booktitle = {35th International Conference on Concurrency Theory (CONCUR 2024)}, pages = {35:1--35:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-339-3}, ISSN = {1868-8969}, year = {2024}, volume = {311}, editor = {Majumdar, Rupak 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.CONCUR.2024.35}, URN = {urn:nbn:de:0030-drops-208071}, doi = {10.4230/LIPIcs.CONCUR.2024.35}, annote = {Keywords: Data languages, tree automata, nominal automata, inclusion checking} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, and Thomas Zeume. Query Maintenance Under Batch Changes with Small-Depth Circuits. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{datta_et_al:LIPIcs.MFCS.2024.46, author = {Datta, Samir and Khan, Asif and Mukherjee, Anish and Tschirbs, Felix and Vortmeier, Nils and Zeume, Thomas}, title = {{Query Maintenance Under Batch Changes with Small-Depth Circuits}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {46:1--46:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.46}, URN = {urn:nbn:de:0030-drops-206027}, doi = {10.4230/LIPIcs.MFCS.2024.46}, annote = {Keywords: Dynamic complexity theory, parallel computation, dynamic algorithms} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Julien Grange, Fabian Vehlken, Nils Vortmeier, and Thomas Zeume. Specification and Automatic Verification of Computational Reductions. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{grange_et_al:LIPIcs.MFCS.2024.56, author = {Grange, Julien and Vehlken, Fabian and Vortmeier, Nils and Zeume, Thomas}, title = {{Specification and Automatic Verification of Computational Reductions}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {56:1--56:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.56}, URN = {urn:nbn:de:0030-drops-206122}, doi = {10.4230/LIPIcs.MFCS.2024.56}, annote = {Keywords: Computational reductions, automatic verification, decidability} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Samir Datta, Asif Khan, and Anish Mukherjee. Dynamic Planar Embedding Is in DynFO. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{datta_et_al:LIPIcs.MFCS.2023.39, author = {Datta, Samir and Khan, Asif and Mukherjee, Anish}, title = {{Dynamic Planar Embedding Is in DynFO}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.39}, URN = {urn:nbn:de:0030-drops-185736}, doi = {10.4230/LIPIcs.MFCS.2023.39}, annote = {Keywords: Dynamic Complexity, Planar graphs, Planar embedding} }
Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)
Felix Tschirbs, Nils Vortmeier, and Thomas Zeume. Dynamic Complexity of Regular Languages: Big Changes, Small Work. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{tschirbs_et_al:LIPIcs.CSL.2023.35, author = {Tschirbs, Felix and Vortmeier, Nils and Zeume, Thomas}, title = {{Dynamic Complexity of Regular Languages: Big Changes, Small Work}}, booktitle = {31st EACSL Annual Conference on Computer Science Logic (CSL 2023)}, pages = {35:1--35:19}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.35}, URN = {urn:nbn:de:0030-drops-174963}, doi = {10.4230/LIPIcs.CSL.2023.35}, annote = {Keywords: dynamic descriptive complexity, regular languages, batch changes, work} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, and Raghunath Tewari. Dynamic Meta-Theorems for Distance and Matching. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 118:1-118:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{datta_et_al:LIPIcs.ICALP.2022.118, author = {Datta, Samir and Gupta, Chetan and Jain, Rahul and Mukherjee, Anish and Sharma, Vimal Raj and Tewari, Raghunath}, title = {{Dynamic Meta-Theorems for Distance and Matching}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {118:1--118: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.118}, URN = {urn:nbn:de:0030-drops-164598}, doi = {10.4230/LIPIcs.ICALP.2022.118}, annote = {Keywords: Dynamic Complexity, Distance, Matching, Derandomization, Isolation, Matrix Rank} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, and Thomas Zeume. Dynamic Complexity of Reachability: How Many Changes Can We Handle?. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 122:1-122:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{datta_et_al:LIPIcs.ICALP.2020.122, author = {Datta, Samir and Kumar, Pankaj and Mukherjee, Anish and Tawari, Anuj and Vortmeier, Nils and Zeume, Thomas}, title = {{Dynamic Complexity of Reachability: How Many Changes Can We Handle?}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {122:1--122:19}, 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.122}, URN = {urn:nbn:de:0030-drops-125291}, doi = {10.4230/LIPIcs.ICALP.2020.122}, annote = {Keywords: Dynamic complexity, reachability, complex changes} }
Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)
Dominik D. Freydenberger and Sam M. Thompson. Dynamic Complexity of Document Spanners. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{freydenberger_et_al:LIPIcs.ICDT.2020.11, author = {Freydenberger, Dominik D. and Thompson, Sam M.}, title = {{Dynamic Complexity of Document Spanners}}, booktitle = {23rd International Conference on Database Theory (ICDT 2020)}, pages = {11:1--11:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-139-9}, ISSN = {1868-8969}, year = {2020}, volume = {155}, editor = {Lutz, Carsten and Jung, Jean Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.11}, URN = {urn:nbn:de:0030-drops-119355}, doi = {10.4230/LIPIcs.ICDT.2020.11}, annote = {Keywords: Document spanners, information extraction, dynamic complexity, descriptive complexity, word equations} }
Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)
Gaetano Geck, Frank Neven, and Thomas Schwentick. Distribution Constraints: The Chase for Distributed Data. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{geck_et_al:LIPIcs.ICDT.2020.13, author = {Geck, Gaetano and Neven, Frank and Schwentick, Thomas}, title = {{Distribution Constraints: The Chase for Distributed Data}}, booktitle = {23rd International Conference on Database Theory (ICDT 2020)}, pages = {13:1--13:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-139-9}, ISSN = {1868-8969}, year = {2020}, volume = {155}, editor = {Lutz, Carsten and Jung, Jean Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.13}, URN = {urn:nbn:de:0030-drops-119378}, doi = {10.4230/LIPIcs.ICDT.2020.13}, annote = {Keywords: tuple-generating dependencies, chase, conjunctive queries, distributed evaluation} }
Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Jonas Schmidt, Thomas Schwentick, Nils Vortmeier, Thomas Zeume, and Ioannis Kokkinis. Dynamic Complexity Meets Parameterised Algorithms. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{schmidt_et_al:LIPIcs.CSL.2020.36, author = {Schmidt, Jonas and Schwentick, Thomas and Vortmeier, Nils and Zeume, Thomas and Kokkinis, Ioannis}, title = {{Dynamic Complexity Meets Parameterised Algorithms}}, booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)}, pages = {36:1--36:17}, 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.36}, URN = {urn:nbn:de:0030-drops-116792}, doi = {10.4230/LIPIcs.CSL.2020.36}, annote = {Keywords: Dynamic complexity, parameterised complexity} }
Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Nils Vortmeier and Thomas Zeume. Dynamic Complexity of Parity Exists Queries. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{vortmeier_et_al:LIPIcs.CSL.2020.37, author = {Vortmeier, Nils and Zeume, Thomas}, title = {{Dynamic Complexity of Parity Exists Queries}}, booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)}, pages = {37:1--37: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.37}, URN = {urn:nbn:de:0030-drops-116805}, doi = {10.4230/LIPIcs.CSL.2020.37}, annote = {Keywords: Dynamic complexity, parity quantifier, arity hierarchy} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Samir Datta, Anish Mukherjee, Nils Vortmeier, and Thomas Zeume. Reachability and Distances under Multiple Changes. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 120:1-120:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{datta_et_al:LIPIcs.ICALP.2018.120, author = {Datta, Samir and Mukherjee, Anish and Vortmeier, Nils and Zeume, Thomas}, title = {{Reachability and Distances under Multiple Changes}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {120:1--120:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.120}, URN = {urn:nbn:de:0030-drops-91245}, doi = {10.4230/LIPIcs.ICALP.2018.120}, annote = {Keywords: dynamic complexity, reachability, distances, complex changes} }
Published in: LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018)
Thomas Zeume. An Update on Dynamic Complexity Theory. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{zeume:LIPIcs.ICDT.2018.3, author = {Zeume, Thomas}, title = {{An Update on Dynamic Complexity Theory}}, booktitle = {21st International Conference on Database Theory (ICDT 2018)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-063-7}, ISSN = {1868-8969}, year = {2018}, volume = {98}, editor = {Kimelfeld, Benny and Amsterdamer, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.3}, URN = {urn:nbn:de:0030-drops-86117}, doi = {10.4230/LIPIcs.ICDT.2018.3}, annote = {Keywords: Dynamic descriptive complexity, SQL updates, Reachability} }
Published in: LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018)
Pablo Barceló, Miguel Romero, and Thomas Zeume. A More General Theory of Static Approximations for Conjunctive Queries. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{barcelo_et_al:LIPIcs.ICDT.2018.7, author = {Barcel\'{o}, Pablo and Romero, Miguel and Zeume, Thomas}, title = {{A More General Theory of Static Approximations for Conjunctive Queries}}, booktitle = {21st International Conference on Database Theory (ICDT 2018)}, pages = {7:1--7:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-063-7}, ISSN = {1868-8969}, year = {2018}, volume = {98}, editor = {Kimelfeld, Benny and Amsterdamer, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.7}, URN = {urn:nbn:de:0030-drops-86021}, doi = {10.4230/LIPIcs.ICDT.2018.7}, annote = {Keywords: conjunctive queries, hypertreewidth, approximations, pebble games} }
Feedback for Dagstuhl Publishing