LIPIcs, Volume 48
ICDT 2016, March 15-18, 2016, Bordeaux, France
Editors: Wim Martens and Thomas Zeume
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} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. A Strategy for Dynamic Programs: Start over and Muddle Through. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 98:1-98:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{datta_et_al:LIPIcs.ICALP.2017.98, author = {Datta, Samir and Mukherjee, Anish and Schwentick, Thomas and Vortmeier, Nils and Zeume, Thomas}, title = {{A Strategy for Dynamic Programs: Start over and Muddle Through}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {98:1--98:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian 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.ICALP.2017.98}, URN = {urn:nbn:de:0030-drops-74470}, doi = {10.4230/LIPIcs.ICALP.2017.98}, annote = {Keywords: dynamic complexity, treewidth, monadic second order logic} }
Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)
Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. Dynamic Complexity under Definable Changes. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{schwentick_et_al:LIPIcs.ICDT.2017.19, author = {Schwentick, Thomas and Vortmeier, Nils and Zeume, Thomas}, title = {{Dynamic Complexity under Definable Changes}}, booktitle = {20th International Conference on Database Theory (ICDT 2017)}, pages = {19:1--19:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-024-8}, ISSN = {1868-8969}, year = {2017}, volume = {68}, editor = {Benedikt, Michael and Orsi, Giorgio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.19}, URN = {urn:nbn:de:0030-drops-70596}, doi = {10.4230/LIPIcs.ICDT.2017.19}, annote = {Keywords: dynamic descriptive complexity, SQL updates, dynamic programs} }
Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)
19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@Proceedings{martens_et_al:LIPIcs.ICDT.2016, title = {{LIPIcs, Volume 48, ICDT'16, Complete Volume}}, booktitle = {19th International Conference on Database Theory (ICDT 2016)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-002-6}, ISSN = {1868-8969}, year = {2016}, volume = {48}, editor = {Martens, Wim and Zeume, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016}, URN = {urn:nbn:de:0030-drops-57991}, doi = {10.4230/LIPIcs.ICDT.2016}, annote = {Keywords: Database Management, Normal forms, Schema and subschema, Query languages, Query processing, Relational databases, Distributed databases, Heterogeneous Databases, Online Information Services,Miscellaneous – Privacy, Office Automation: Workflow management} }