Search Results

Documents authored by Schwentick, Thomas

Document
DOI: 10.4230/LIPIcs.MFCS.2023.80
Dynamic Constant Time Parallel Graph Algorithms with Sub-Linear Work

Authors: Jonas Schmidt and Thomas Schwentick

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
The paper proposes dynamic parallel algorithms for connectivity and bipartiteness of undirected graphs that require constant time and 𝒪(n^{1/2+ε}) work on the CRCW PRAM model. The work of these algorithms almost matches the work of the 𝒪(log n) time algorithm for connectivity by Kopelowitz et al. (2018) on the EREW PRAM model and the time of the sequential algorithm for bipartiteness by Eppstein et al. (1997). In particular, we show that the sparsification technique, which has been used in both mentioned papers, can in principle also be used for constant time algorithms in the CRCW PRAM model, despite the logarithmic depth of sparsification trees.
Cite as

Jonas Schmidt and Thomas Schwentick. Dynamic Constant Time Parallel Graph Algorithms with Sub-Linear Work. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 80:1-80:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{schmidt_et_al:LIPIcs.MFCS.2023.80,
  author =	{Schmidt, Jonas and Schwentick, Thomas},
  title =	{{Dynamic Constant Time Parallel Graph Algorithms with Sub-Linear Work}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{80:1--80: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.80},
  URN =		{urn:nbn:de:0030-drops-186140},
  doi =		{10.4230/LIPIcs.MFCS.2023.80},
  annote =	{Keywords: Dynamic parallel algorithms, Undirected connectivity, Bipartiteness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.81
On the Work of Dynamic Constant-Time Parallel Algorithms for Regular Tree Languages and Context-Free Languages

Authors: Jonas Schmidt, Thomas Schwentick, and Jennifer Todtenhoefer

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Previous work on Dynamic Complexity has established that there exist dynamic constant-time parallel algorithms for regular tree languages and context-free languages under label or symbol changes. However, these algorithms were not developed with the goal to minimise work (or, equivalently, the number of processors). In fact, their inspection yields the work bounds 𝒪(n²) and 𝒪(n⁷) per change operation, respectively. In this paper, dynamic algorithms for regular tree languages are proposed that generalise the previous algorithms in that they allow unbounded node rank and leaf insertions, while improving the work bound from 𝒪(n²) to 𝒪(n^ε), for arbitrary ε > 0. For context-free languages, algorithms with better work bounds (compared with 𝒪(n⁷)) for restricted classes are proposed: for every ε > 0 there are such algorithms for deterministic context-free languages with work bound 𝒪(n^{3+ε}) and for visibly pushdown languages with work bound 𝒪(n^{2+ε}).
Cite as

Jonas Schmidt, Thomas Schwentick, and Jennifer Todtenhoefer. On the Work of Dynamic Constant-Time Parallel Algorithms for Regular Tree Languages and Context-Free Languages. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 81:1-81:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{schmidt_et_al:LIPIcs.MFCS.2023.81,
  author =	{Schmidt, Jonas and Schwentick, Thomas and Todtenhoefer, Jennifer},
  title =	{{On the Work of Dynamic Constant-Time Parallel Algorithms for Regular Tree Languages and Context-Free Languages}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{81:1--81: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.81},
  URN =		{urn:nbn:de:0030-drops-186152},
  doi =		{10.4230/LIPIcs.MFCS.2023.81},
  annote =	{Keywords: Dynamic complexity, work, parallel constant time}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2023.16
Work-Efficient Query Evaluation with PRAMs

Authors: Jens Keppeler, Thomas Schwentick, and Christopher Spinrath

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
The paper studies query evaluation in parallel constant time in the PRAM model. While it is well-known that all relational algebra queries can be evaluated in constant time on an appropriate CRCW-PRAM, this paper is interested in the efficiency of evaluation algorithms, that is, in the number of processors or, asymptotically equivalent, in the work. Naive evaluation in the parallel setting results in huge (polynomial) bounds on the work of such algorithms and in presentations of the result sets that can be extremely scattered in memory. The paper first discusses some obstacles for constant time PRAM query evaluation. It presents algorithms for relational operators that are considerably more efficient than the naive approaches. Further it explores three settings, in which efficient sequential query evaluation algorithms exist: acyclic queries, semi-join algebra queries, and join queries - the latter in the worst-case optimal framework. Under natural assumptions on the representation of the database, the work of the given algorithms matches the best sequential algorithms in the case of semi-join queries, and it comes close in the other two settings. An important tool is the compaction technique from Hagerup (1992).
Cite as

Jens Keppeler, Thomas Schwentick, and Christopher Spinrath. Work-Efficient Query Evaluation with PRAMs. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{keppeler_et_al:LIPIcs.ICDT.2023.16,
  author =	{Keppeler, Jens and Schwentick, Thomas and Spinrath, Christopher},
  title =	{{Work-Efficient Query Evaluation with PRAMs}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.16},
  URN =		{urn:nbn:de:0030-drops-177589},
  doi =		{10.4230/LIPIcs.ICDT.2023.16},
  annote =	{Keywords: PRAM, query evaluation, work-efficient, parallel, acyclic queries, free-connex queries}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.38
Low-Latency Sliding Window Algorithms for Formal Languages

Authors: Moses Ganardi, Louis Jachiet, Markus Lohrey, and Thomas Schwentick

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Low-latency sliding window algorithms for regular and context-free languages are studied, where latency refers to the worst-case time spent for a single window update or query. For every regular language L it is shown that there exists a constant-latency solution that supports adding and removing symbols independently on both ends of the window (the so-called two-way variable-size model). We prove that this result extends to all visibly pushdown languages. For deterministic 1-counter languages we present a 𝒪(log n) latency sliding window algorithm for the two-way variable-size model where n refers to the window size. We complement these results with a conditional lower bound: there exists a fixed real-time deterministic context-free language L such that, assuming the OMV (online matrix vector multiplication) conjecture, there is no sliding window algorithm for L with latency n^(1/2-ε) for any ε > 0, even in the most restricted sliding window model (one-way fixed-size model). The above mentioned results all refer to the unit-cost RAM model with logarithmic word size. For regular languages we also present a refined picture using word sizes 𝒪(1), 𝒪(log log n), and 𝒪(log n).
Cite as

Moses Ganardi, Louis Jachiet, Markus Lohrey, and Thomas Schwentick. Low-Latency Sliding Window Algorithms for Formal Languages. 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. 38:1-38:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.FSTTCS.2022.38,
  author =	{Ganardi, Moses and Jachiet, Louis and Lohrey, Markus and Schwentick, Thomas},
  title =	{{Low-Latency Sliding Window Algorithms for Formal Languages}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{38:1--38: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.38},
  URN =		{urn:nbn:de:0030-drops-174301},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.38},
  annote =	{Keywords: Streaming algorithms, regular languages, context-free languages}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2022.8
Rewriting with Acyclic Queries: Mind Your Head

Authors: Gaetano Geck, Jens Keppeler, Thomas Schwentick, and Christopher Spinrath

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

Abstract
The paper studies the rewriting problem, that is, the decision problem whether, for a given conjunctive query Q and a set 𝒱 of views, there is a conjunctive query Q' over 𝒱 that is equivalent to Q, for cases where the query, the views, and/or the desired rewriting are acyclic or even more restricted. It shows that, if Q itself is acyclic, an acyclic rewriting exists if there is any rewriting. An analogous statement also holds for free-connex acyclic, hierarchical, and q-hierarchical queries. Regarding the complexity of the rewriting problem, the paper identifies a border between tractable and (presumably) intractable variants of the rewriting problem: for schemas of bounded arity, the acyclic rewriting problem is NP-hard, even if both Q and the views in 𝒱 are acyclic or hierarchical. However, it becomes tractable, if the views are free-connex acyclic (i.e., in a nutshell, their body is (i) acyclic and (ii) remains acyclic if their head is added as an additional atom).
Cite as

Gaetano Geck, Jens Keppeler, Thomas Schwentick, and Christopher Spinrath. Rewriting with Acyclic Queries: Mind Your Head. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{geck_et_al:LIPIcs.ICDT.2022.8,
  author =	{Geck, Gaetano and Keppeler, Jens and Schwentick, Thomas and Spinrath, Christopher},
  title =	{{Rewriting with Acyclic Queries: Mind Your Head}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.8},
  URN =		{urn:nbn:de:0030-drops-158829},
  doi =		{10.4230/LIPIcs.ICDT.2022.8},
  annote =	{Keywords: rewriting, acyclic rewriting, acyclic conjunctive queries, free-connex queries, hierarchical queries, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2020.13
Distribution Constraints: The Chase for Distributed Data

Authors: Gaetano Geck, Frank Neven, and Thomas Schwentick

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract
This paper introduces a declarative framework to specify and reason about distributions of data over computing nodes in a distributed setting. More specifically, it proposes distribution constraints which are tuple and equality generating dependencies (tgds and egds) extended with node variables ranging over computing nodes. In particular, they can express co-partitioning constraints and constraints about range-based data distributions by using comparison atoms. The main technical contribution is the study of the implication problem of distribution constraints. While implication is undecidable in general, relevant fragments of so-called data-full constraints are exhibited for which the corresponding implication problems are complete for EXPTIME, PSPACE and NP. These results yield bounds on deciding parallel-correctness for conjunctive queries in the presence of distribution constraints.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.CSL.2020.36
Dynamic Complexity Meets Parameterised Algorithms

Authors: Jonas Schmidt, Thomas Schwentick, Nils Vortmeier, Thomas Zeume, and Ioannis Kokkinis

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract
Dynamic Complexity studies the maintainability of queries with logical formulas in a setting where the underlying structure or database changes over time. Most often, these formulas are from first-order logic, giving rise to the dynamic complexity class DynFO. This paper investigates extensions of DynFO in the spirit of parameterised algorithms. In this setting structures come with a parameter k and the extensions allow additional "space" of size f(k) (in the form of an additional structure of this size) or additional time f(k) (in the form of iterations of formulas) or both. The resulting classes are compared with their non-dynamic counterparts and other classes. The main part of the paper explores the applicability of methods for parameterised algorithms to this setting through case studies for various well-known parameterised problems.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2019.14
Parallel-Correctness and Parallel-Boundedness for Datalog Programs

Authors: Frank Neven, Thomas Schwentick, Christopher Spinrath, and Brecht Vandevoort

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract
Recently, Ketsman et al. started the investigation of the parallel evaluation of recursive queries in the Massively Parallel Communication (MPC) model. Among other things, it was shown that parallel-correctness and parallel-boundedness for general Datalog programs is undecidable, by a reduction from the undecidable containment problem for Datalog. Furthermore, economic policies were introduced as a means to specify data distribution in a recursive setting. In this paper, we extend the latter framework to account for more general distributed evaluation strategies in terms of communication policies. We then show that the undecidability of parallel-correctness runs deeper: it already holds for fragments of Datalog, e.g., monadic and frontier-guarded Datalog, with a decidable containment problem, under relatively simple evaluation strategies. These simple evaluation strategies are defined w.r.t. data-moving distribution constraints. We then investigate restrictions of economic policies that yield decidability. In particular, we show that parallel-correctness is 2EXPTIME-complete for monadic and frontier-guarded Datalog under hash-based economic policies. Next, we consider restrictions of data-moving constraints and show that parallel-correctness and parallel-boundedness are 2EXPTIME-complete for frontier-guarded Datalog. Interestingly, distributed evaluation no longer preserves the usual containment relationships between fragments of Datalog. Indeed, not every monadic Datalog program is equivalent to a frontier-guarded one in the distributed setting. We illustrate the latter by considering two alternative settings where in one of these parallel-correctness is decidable for frontier-guarded Datalog but undecidable for monadic Datalog.
Cite as

Frank Neven, Thomas Schwentick, Christopher Spinrath, and Brecht Vandevoort. Parallel-Correctness and Parallel-Boundedness for Datalog Programs. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{neven_et_al:LIPIcs.ICDT.2019.14,
  author =	{Neven, Frank and Schwentick, Thomas and Spinrath, Christopher and Vandevoort, Brecht},
  title =	{{Parallel-Correctness and Parallel-Boundedness for Datalog Programs}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.14},
  URN =		{urn:nbn:de:0030-drops-103165},
  doi =		{10.4230/LIPIcs.ICDT.2019.14},
  annote =	{Keywords: Datalog, distributed databases, distributed evaluation, decision problems, complexity}
}
Document
DOI: 10.4230/LIPIcs.CSL.2018.1
The Ackermann Award 2018

Authors: Dexter Kozen and Thomas Schwentick

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

Abstract
The Ackermann Award is the EACSL Outstanding Dissertation Award for Logic in Computer Science. It is presented during the annual conference of the EACSL (CSL'xx). This contribution reports on the 2018 edition of the award.
Cite as

Dexter Kozen and Thomas Schwentick. The Ackermann Award 2018. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 1:1-1:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kozen_et_al:LIPIcs.CSL.2018.1,
  author =	{Kozen, Dexter and Schwentick, Thomas},
  title =	{{The Ackermann Award 2018}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
  pages =	{1:1--1:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.1},
  URN =		{urn:nbn:de:0030-drops-96686},
  doi =		{10.4230/LIPIcs.CSL.2018.1},
  annote =	{Keywords: Ackermann Award}
}
Document
DOI: 10.4230/DagMan.7.1.1
Research Directions for Principles of Data Management (Dagstuhl Perspectives Workshop 16151)

Authors: Serge Abiteboul, Marcelo Arenas, Pablo Barceló, Meghyn Bienvenu, Diego Calvanese, Claire David, Richard Hull, Eyke Hüllermeier, Benny Kimelfeld, Leonid Libkin, Wim Martens, Tova Milo, Filip Murlak, Frank Neven, Magdalena Ortiz, Thomas Schwentick, Julia Stoyanovich, Jianwen Su, Dan Suciu, Victor Vianu, and Ke Yi

Published in: Dagstuhl Manifestos, Volume 7, Issue 1 (2018)

Abstract
The area of Principles of Data Management (PDM) has made crucial contributions to the development of formal frameworks for understanding and managing data and knowledge. This work has involved a rich cross-fertilization between PDM and other disciplines in mathematics and computer science, including logic, complexity theory, and knowledge representation. We anticipate on-going expansion of PDM research as the technology and applications involving data management continue to grow and evolve. In particular, the lifecycle of Big Data Analytics raises a wealth of challenge areas that PDM can help with. In this report we identify some of the most important research directions where the PDM community has the potential to make significant contributions. This is done from three perspectives: potential practical relevance, results already obtained, and research questions that appear surmountable in the short and medium term.
Cite as

Serge Abiteboul, Marcelo Arenas, Pablo Barceló, Meghyn Bienvenu, Diego Calvanese, Claire David, Richard Hull, Eyke Hüllermeier, Benny Kimelfeld, Leonid Libkin, Wim Martens, Tova Milo, Filip Murlak, Frank Neven, Magdalena Ortiz, Thomas Schwentick, Julia Stoyanovich, Jianwen Su, Dan Suciu, Victor Vianu, and Ke Yi. Research Directions for Principles of Data Management (Dagstuhl Perspectives Workshop 16151). In Dagstuhl Manifestos, Volume 7, Issue 1, pp. 1-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{abiteboul_et_al:DagMan.7.1.1,
  author =	{Abiteboul, Serge and Arenas, Marcelo and Barcel\'{o}, Pablo and Bienvenu, Meghyn and Calvanese, Diego and David, Claire and Hull, Richard and H\"{u}llermeier, Eyke and Kimelfeld, Benny and Libkin, Leonid and Martens, Wim and Milo, Tova and Murlak, Filip and Neven, Frank and Ortiz, Magdalena and Schwentick, Thomas and Stoyanovich, Julia and Su, Jianwen and Suciu, Dan and Vianu, Victor and Yi, Ke},
  title =	{{Research Directions for Principles of Data Management (Dagstuhl Perspectives Workshop 16151)}},
  pages =	{1--29},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2018},
  volume =	{7},
  number =	{1},
  editor =	{Abiteboul, Serge and Arenas, Marcelo and Barcel\'{o}, Pablo and Bienvenu, Meghyn and Calvanese, Diego and David, Claire and Hull, Richard and H\"{u}llermeier, Eyke and Kimelfeld, Benny and Libkin, Leonid and Martens, Wim and Milo, Tova and Murlak, Filip and Neven, Frank and Ortiz, Magdalena and Schwentick, Thomas and Stoyanovich, Julia and Su, Jianwen and Suciu, Dan and Vianu, Victor and Yi, Ke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagMan.7.1.1},
  URN =		{urn:nbn:de:0030-drops-86772},
  doi =		{10.4230/DagMan.7.1.1},
  annote =	{Keywords: database theory, principles of data management, query languages, efficient query processing, query optimization, heterogeneous data, uncertainty, knowledge-enriched data management, machine learning, workflows, human-related data, ethics}
}
Document
DOI: 10.4230/DagRep.7.9.1
Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361)

Authors: Anuj Dawar, Erich Grädel, Phokion G. Kolaitis, and Thomas Schwentick

Published in: Dagstuhl Reports, Volume 7, Issue 9 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17361 "Finite and Algorithmic Model Theory".
Cite as

Anuj Dawar, Erich Grädel, Phokion G. Kolaitis, and Thomas Schwentick. Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361). In Dagstuhl Reports, Volume 7, Issue 9, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{dawar_et_al:DagRep.7.9.1,
  author =	{Dawar, Anuj and Gr\"{a}del, Erich and Kolaitis, Phokion G. and Schwentick, Thomas},
  title =	{{Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361)}},
  pages =	{1--25},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{9},
  editor =	{Dawar, Anuj and Gr\"{a}del, Erich and Kolaitis, Phokion G. and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.9.1},
  URN =		{urn:nbn:de:0030-drops-85863},
  doi =		{10.4230/DagRep.7.9.1},
  annote =	{Keywords: algorithms, database theory, descriptive complexity, finite model theory, independence logic, knowledge representation, model checking}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.98
A Strategy for Dynamic Programs: Start over and Muddle Through

Authors: Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
A strategy for constructing dynamic programs is introduced that utilises periodic computation of auxiliary data from scratch and the ability to maintain a query for a limited number of change steps. It is established that if some program can maintain a query for log n change steps after an AC^1-computable initialisation, it can be maintained by a first-order dynamic program as well, i.e., in DynFO. As an application, it is shown that decision and optimisation problems defined by monadic second-order (MSO) and guarded second-order logic (GSO) formulas are in DynFO, if only change sequences that produce graphs of bounded treewidth are allowed. To establish this result, Feferman-Vaught-type composition theorems for MSO and GSO are established that might be useful in their own right.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.19
Dynamic Complexity under Definable Changes

Authors: Thomas Schwentick, Nils Vortmeier, and Thomas Zeume

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
This paper studies dynamic complexity under definable change operations in the DynFO framework by Patnaik and Immerman. It is shown that for changes definable by parameter-free first-order formulas, all (uniform) AC1 queries can be maintained by first-order dynamic programs. Furthermore, many maintenance results for single-tuple changes are extended to more powerful change operations: (1) The reachability query for undirected graphs is first-order maintainable under single tuple changes and first-order defined insertions, likewise the reachability query for directed acyclic graphs under quantifier-free insertions. (2) Context-free languages are first-order maintainable under \EFO-defined changes. These results are complemented by several inexpressibility results, for example, that the reachability query cannot be maintained by quantifier-free programs under definable, quantifier-free deletions.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/DagRep.6.4.39
Foundations of Data Management (Dagstuhl Perspectives Workshop 16151)

Authors: Marcelo Arenas, Richard Hull, Wim Marten, Tova Milo, and Thomas Schwentick

Published in: Dagstuhl Reports, Volume 6, Issue 4 (2016)

Abstract
In this Workshop we have explored the degree to which principled foundations are crucial to the long-term success and effectiveness of the new generation of data management paradigms and applications, and investigated what forms of research need to be pursued to develop and advance these foundations. The workshop brought together specialists from the existing database theory community, and from adjoining areas, particularly from various subdisciplines within the Big Data community, to understand the challenge areas that might be resolved through principled foundations and mathematical theory.
Cite as

Marcelo Arenas, Richard Hull, Wim Marten, Tova Milo, and Thomas Schwentick. Foundations of Data Management (Dagstuhl Perspectives Workshop 16151). In Dagstuhl Reports, Volume 6, Issue 4, pp. 39-56, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{arenas_et_al:DagRep.6.4.39,
  author =	{Arenas, Marcelo and Hull, Richard and Marten, Wim and Milo, Tova and Schwentick, Thomas},
  title =	{{Foundations of Data Management (Dagstuhl Perspectives Workshop 16151)}},
  pages =	{39--56},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{4},
  editor =	{Arenas, Marcelo and Hull, Richard and Marten, Wim and Milo, Tova and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.4.39},
  URN =		{urn:nbn:de:0030-drops-61526},
  doi =		{10.4230/DagRep.6.4.39},
  annote =	{Keywords: Foundations of data management, Principles of databases}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2016.9
Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation

Authors: Gaetano Geck, Bas Ketsman, Frank Neven, and Thomas Schwentick

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)

Abstract
Single-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing a given query, also referred to as parallel-correctness. This paper extends the study of the complexity of parallel-correctness and its constituents, parallel-soundness and parallel-completeness, to unions of conjunctive queries with and without negation. As a by-product it is shown that the containment problem for conjunctive queries with negation is coNEXPTIME-complete.
Cite as

Gaetano Geck, Bas Ketsman, Frank Neven, and Thomas Schwentick. Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{geck_et_al:LIPIcs.ICDT.2016.9,
  author =	{Geck, Gaetano and Ketsman, Bas and Neven, Frank and Schwentick, Thomas},
  title =	{{Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{9:1--9:17},
  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.9},
  URN =		{urn:nbn:de:0030-drops-57787},
  doi =		{10.4230/LIPIcs.ICDT.2016.9},
  annote =	{Keywords: Conjunctive queries, distributed evaluation}
}
Document
DOI: 10.4230/DagRep.5.9.105
Circuits, Logic and Games (Dagstuhl Seminar 15401)

Authors: Mikolaj Bojanczyk, Meena Mahajan, Thomas Schwentick, and Heribert Vollmer

Published in: Dagstuhl Reports, Volume 5, Issue 9 (2016)

Abstract
Over the years, there has been a lot of interplay between circuit complexity and logic. There are tight connections between small-depth circuit classes and fragments and extensions of firstorder logic, and ideas from games and finite model theory have provided powerful lower bound techniques for circuits. In recent years, there has been an impressive and sustained growth of interest and activity in the intersection of finite model theory and Boolean circuit complexity. The central aim of the seminar was to bring together researchers from these two areas to further strengthen the mutual fertilisation. The seminar focussed on the following specific topics: -The algebraic approach to circuit complexity with its applications to finite model theory -The logic-circuit connection, with a particular emphasis on circuit lower bounds that trigger results in finite model theory like separations between logics - New connections between uniformity conditions on circuit families and logical predicates - Structural complexity and circuit lower bounds inherently using methods from logic and algebra Proof systems with low circuit complexity - Dynamic complexity: understanding the dynamic expressive power of small depth circuit classes The seminar had 43 participants from 11 countries and was very successful with respect to the exchange of recent results, ideas and methodological approaches.
Cite as

Mikolaj Bojanczyk, Meena Mahajan, Thomas Schwentick, and Heribert Vollmer. Circuits, Logic and Games (Dagstuhl Seminar 15401). In Dagstuhl Reports, Volume 5, Issue 9, pp. 105-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{bojanczyk_et_al:DagRep.5.9.105,
  author =	{Bojanczyk, Mikolaj and Mahajan, Meena and Schwentick, Thomas and Vollmer, Heribert},
  title =	{{Circuits, Logic and Games (Dagstuhl Seminar 15401)}},
  pages =	{105--124},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{9},
  editor =	{Bojanczyk, Mikolaj and Mahajan, Meena and Schwentick, Thomas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.9.105},
  URN =		{urn:nbn:de:0030-drops-56872},
  doi =		{10.4230/DagRep.5.9.105},
  annote =	{Keywords: computational complexity theory, finite model theory, Boolean circuits, regular languages, finite monoids, Ehrenfeucht-Fraiss\'{e}-games}
}
Document
DOI: 10.4230/LIPIcs.CSL.2015.308
Static Analysis for Logic-based Dynamic Programs

Authors: Thomas Schwentick, Nils Vortmeier, and Thomas Zeume

Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)

Abstract
The goal of dynamic programs as introduced by Patnaik and Immerman (1994) is to maintain the result of a fixed query for an input database which is subject to tuple insertions and deletions. To this end such programs store an auxiliary database whose relations are updated via first-order formulas upon modifications of the input database. One of those auxiliary relations is supposed to store the answer to the query. Several static analysis problems can be associated to such dynamic programs. Is the answer relation of a given dynamic program always empty? Does a program actually maintain a query? That is, is the answer given of the program the same when an input database was reached by two different modification sequences? Even more, is the content of auxiliary relations independent of the modification sequence that lead to an input database? We study the algorithmic properties of those and similar static analysis problems. Since all these problems can easily be seen to be undecidable for full first-order programs, we examine the exact borderline for decidability for restricted programs. Our focus is on restricting the arity of the input databases as well as the auxiliary databases, and to restrict the use of quantifiers.
Cite as

Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. Static Analysis for Logic-based Dynamic Programs. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 308-324, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{schwentick_et_al:LIPIcs.CSL.2015.308,
  author =	{Schwentick, Thomas and Vortmeier, Nils and Zeume, Thomas},
  title =	{{Static Analysis for Logic-based Dynamic Programs}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{308--324},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Kreutzer, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.308},
  URN =		{urn:nbn:de:0030-drops-54221},
  doi =		{10.4230/LIPIcs.CSL.2015.308},
  annote =	{Keywords: Dynamic descriptive complexity, algorithmic problems, emptiness, history independence, consistency}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2015.60
Games for Active XML Revisited

Authors: Martin Schuster and Thomas Schwentick

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)

Abstract
The paper studies the rewriting mechanisms for intensional documents in the Active XML framework, abstracted in the form of active context-free games. The safe rewriting problem studied in this paper is to decide whether the first player, Juliet, has a winning strategy for a given game and (nested) word; this corresponds to a successful rewriting strategy for a given intensional document. The paper examines several extensions to active context-free games. The primary extension allows more expressive schemas (namely XML schemas and regular nested word languages) for both target and replacement languages and has the effect that games are played on nested words instead of (flat) words as in previous studies. Other extensions consider validation of input parameters of web services, and an alternative semantics based on insertion of service call results. In general, the complexity of the safe rewriting problem is highly intractable (doubly exponential time), but the paper identifies interesting tractable cases.
Cite as

Martin Schuster and Thomas Schwentick. Games for Active XML Revisited. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 60-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{schuster_et_al:LIPIcs.ICDT.2015.60,
  author =	{Schuster, Martin and Schwentick, Thomas},
  title =	{{Games for Active XML Revisited}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{60--75},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.60},
  URN =		{urn:nbn:de:0030-drops-49773},
  doi =		{10.4230/LIPIcs.ICDT.2015.60},
  annote =	{Keywords: Active XML, Computational Complexity, Nested Words, Rewriting Games, Semistructured Data}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2010
LIPIcs, Volume 5, STACS'10, Complete Volume

Authors: Jean-Yves Marion and Thomas Schwentick

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
LIPIcs, Volume 5, STACS'10, Complete Volume
Cite as

27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{marion_et_al:LIPIcs.STACS.2010,
  title =	{{LIPIcs, Volume 5, STACS'10, Complete Volume}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010},
  URN =		{urn:nbn:de:0030-drops-40996},
  doi =		{10.4230/LIPIcs.STACS.2010},
  annote =	{Keywords: LIPIcs, Volume 5, STACS'10, Complete Volume}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2011
LIPIcs, Volume 9, STACS'11, Complete Volume

Authors: Thomas Schwentick and Christoph Dürr

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
LIPIcs, Volume 9, STACS'11, Complete Volume
Cite as

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{schwentick_et_al:LIPIcs.STACS.2011,
  title =	{{LIPIcs, Volume 9, STACS'11, Complete Volume}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011},
  URN =		{urn:nbn:de:0030-drops-41031},
  doi =		{10.4230/LIPIcs.STACS.2011},
  annote =	{Keywords: Models of Computation, Nonnumerical Algorithms and Problems, Mathematical Logic, Formal Languages, Combinatorics, Graph Theory}
}
Document
DOI: 10.4230/DagRep.1.10.37
Foundations of distributed data management (Dagstuhl Seminar 11421)

Authors: Serge Abiteboul, Alin Deutsch, Thomas Schwentick, and Luc Segoufin

Published in: Dagstuhl Reports, Volume 1, Issue 10 (2012)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 11421 ``Foundations of distributed data management''.
Cite as

Serge Abiteboul, Alin Deutsch, Thomas Schwentick, and Luc Segoufin. Foundations of distributed data management (Dagstuhl Seminar 11421). In Dagstuhl Reports, Volume 1, Issue 10, pp. 37-57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{abiteboul_et_al:DagRep.1.10.37,
  author =	{Abiteboul, Serge and Deutsch, Alin and Schwentick, Thomas and Segoufin, Luc},
  title =	{{Foundations of distributed data management (Dagstuhl Seminar 11421)}},
  pages =	{37--57},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{1},
  number =	{10},
  editor =	{Abiteboul, Serge and Deutsch, Alin and Schwentick, Thomas and Segoufin, Luc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.10.37},
  URN =		{urn:nbn:de:0030-drops-33737},
  doi =		{10.4230/DagRep.1.10.37},
  annote =	{Keywords: XML Query language, Distribution, Incompleteness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.685
Index of Authors

Authors: Thomas Schwentick and Christoph Dürr

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
Author Index.
Cite as

Thomas Schwentick and Christoph Dürr. Index of Authors. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 685-686, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{schwentick_et_al:LIPIcs.STACS.2011.685,
  author =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  title =	{{Index of Authors}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{685--686},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.685},
  URN =		{urn:nbn:de:0030-drops-30542},
  doi =		{10.4230/LIPIcs.STACS.2011.685},
  annote =	{Keywords: Author Index}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2011.i
Frontmatter, Table of Contents, Preface, Conference Organization

Authors: Thomas Schwentick and Christoph Dürr

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
Frontmatter, Table of Contents, Preface, Conference Organization
Cite as

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. i-xvii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{schwentick_et_al:LIPIcs.STACS.2011.i,
  author =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  title =	{{Frontmatter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{i--xvii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.i},
  URN =		{urn:nbn:de:0030-drops-29939},
  doi =		{10.4230/LIPIcs.STACS.2011.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2010.481
Temporal Logics on Words with Multiple Data Values

Authors: Ahmet Kara, Thomas Schwentick, and Thomas Zeume

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Abstract
The paper proposes and studies temporal logics for attributed words, that is, data words with a (finite) set of (attribute,value)-pairs at each position. It considers a basic logic which is a semantical fragment of the logic $\LTL^\downarrow_1$ of Demri and Lazic with operators for navigation into the future and the past. By reduction to the emptiness problem for data automata it is shown that this basic logic is decidable. Whereas the basic logic only allows navigation to positions where a fixed data value occurs, extensions are studied that also allow navigation to positions with different data values. Besides some undecidable results it is shown that the extension by a certain UNTIL-operator with an inequality target condition remains decidable.
Cite as

Ahmet Kara, Thomas Schwentick, and Thomas Zeume. Temporal Logics on Words with Multiple Data Values. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 481-492, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{kara_et_al:LIPIcs.FSTTCS.2010.481,
  author =	{Kara, Ahmet and Schwentick, Thomas and Zeume, Thomas},
  title =	{{Temporal Logics on Words with Multiple Data Values}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{481--492},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.481},
  URN =		{urn:nbn:de:0030-drops-28883},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.481},
  annote =	{Keywords: Expressiveness, Decidability, Temporal Logic, Data words}
}
Document
DOI: 10.4230/DagSemProc.10061.1
10061 Abstracts Collection – Circuits, Logic, and Games

Authors: Benjamin Rossman, Thomas Schwentick, Denis Thérien, and Heribert Vollmer

Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)

Abstract
From 07/02/10 to 12/02/10, the Dagstuhl Seminar 10061 ``Circuits, Logic, and Games '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Benjamin Rossman, Thomas Schwentick, Denis Thérien, and Heribert Vollmer. 10061 Abstracts Collection – Circuits, Logic, and Games. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{rossman_et_al:DagSemProc.10061.1,
  author =	{Rossman, Benjamin and Schwentick, Thomas and Th\'{e}rien, Denis and Vollmer, Heribert},
  title =	{{10061 Abstracts Collection – Circuits, Logic, and Games}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10061},
  editor =	{Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.1},
  URN =		{urn:nbn:de:0030-drops-25280},
  doi =		{10.4230/DagSemProc.10061.1},
  annote =	{Keywords: Computational complexity theory, Finite model theory, Boolean circuits, Regular languages, Finite monoids, Ehrenfeucht-Fra\{\backslash''i\}ss\'{e}-games}
}
Document
DOI: 10.4230/DagSemProc.10061.2
10061 Executive Summary – Circuits, Logic, and Games

Authors: Benjamin Rossman, Thomas Schwentick, Denis Thérien, and Heribert Vollmer

Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)

Abstract
In the same way as during the first seminar on "Circuits, Logic, and Games"(Nov.~2006, 06451), the organizers aimed to bring together researchers from the areas of finite model theory and computational complexity theory, since they felt that perhaps not all developments in circuit theory and in logic had been explored fully in the context of lower bounds. In fact, the interaction between the areas has flourished a lot in the past 2-3 years, as can be exemplified by the following lines of research.
Cite as

Benjamin Rossman, Thomas Schwentick, Denis Thérien, and Heribert Vollmer. 10061 Executive Summary – Circuits, Logic, and Games. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{rossman_et_al:DagSemProc.10061.2,
  author =	{Rossman, Benjamin and Schwentick, Thomas and Th\'{e}rien, Denis and Vollmer, Heribert},
  title =	{{10061 Executive Summary – Circuits, Logic, and Games}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10061},
  editor =	{Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.2},
  URN =		{urn:nbn:de:0030-drops-25279},
  doi =		{10.4230/DagSemProc.10061.2},
  annote =	{Keywords: Computational complexity theory, finite model theory, Boolean circuits, regular languages, finite monoids, Ehrenfeucht-Fra\backslash"\backslashi ss\backslash'e-games}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2505
Table of Contents -- 27th International Symposium on Theoretical Aspects of Computer Science

Authors: Jean-Yves Marion and Thomas Schwentick

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Table of contents
Cite as

Jean-Yves Marion and Thomas Schwentick. Table of Contents -- 27th International Symposium on Theoretical Aspects of Computer Science. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 7-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{marion_et_al:LIPIcs.STACS.2010.2505,
  author =	{Marion, Jean-Yves and Schwentick, Thomas},
  title =	{{Table of Contents -- 27th International Symposium on Theoretical Aspects of Computer Science}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{7--10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2505},
  URN =		{urn:nbn:de:0030-drops-25059},
  doi =		{10.4230/LIPIcs.STACS.2010.2505},
  annote =	{Keywords: Table of contents}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2010.2439
Foreword -- 27th International Symposium on Theoretical Aspects of Computer Science

Authors: Jean-Yves Marion and Thomas Schwentick

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
The STACS conference of March 4-6, 2010, held in Nancy, is the 27th in this series. The STACS 2010 call for papers led to over 238 submissions from 40 countries. Each paper was assigned to three program committee members. The committee selected 54 papers during a two-week electronic meeting held in November.
Cite as

27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. i-vi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{marion_et_al:LIPIcs.STACS.2010.2439,
  author =	{Marion, Jean-Yves and Schwentick, Thomas},
  title =	{{Foreword -- 27th International Symposium on Theoretical Aspects of Computer Science}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{i--vi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2439},
  URN =		{urn:nbn:de:0030-drops-24393},
  doi =		{10.4230/LIPIcs.STACS.2010.2439},
  annote =	{Keywords: Foreword}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1829
The Dynamic Complexity of Formal Languages

Authors: Wouter Gelade, Marcel Marquardt, and Thomas Schwentick

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
The paper investigates the power of the dynamic complexity classes DynFO, DynQF and DynPROP over string languages. The latter two classes contain problems that can be maintained using quantifier-free first-order updates, with and without auxiliary functions, respectively. It is shown that the languages maintainable in DynPROP exactly are the regular languages, even when allowing arbitrary precomputation. This enables lower bounds for DynPROP and separates DynPROP from DynQF and DynFO. Further, it is shown that any context-free language can be maintained in DynFO and a number of specific context-free languages, for example all Dyck-languages, are maintainable in DynQF. Furthermore, the dynamic complexity of regular tree languages is investigated and some results concerning arbitrary structures are obtained: there exist first-order definable properties which are not maintainable in DynPROP. On the other hand any existential first-order property can be maintained in DynQF when allowing precomputation.
Cite as

Wouter Gelade, Marcel Marquardt, and Thomas Schwentick. The Dynamic Complexity of Formal Languages. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 481-492, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{gelade_et_al:LIPIcs.STACS.2009.1829,
  author =	{Gelade, Wouter and Marquardt, Marcel and Schwentick, Thomas},
  title =	{{The Dynamic Complexity of Formal Languages}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{481--492},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1829},
  URN =		{urn:nbn:de:0030-drops-18297},
  doi =		{10.4230/LIPIcs.STACS.2009.1829},
  annote =	{Keywords: Dynamic complexity, Regular languages, Context-free languages, DynFO}
}
Document
DOI: 10.4230/DagSemProc.08171.1
08171 Abstracts Collection – Beyond the Finite: New Challenges in Verification and Semistructured Data

Authors: Anca Muscholl, Ramaswamy Ramanujam, Michaël Rusinowitch, Thomas Schwentick, and Victor Vianu

Published in: Dagstuhl Seminar Proceedings, Volume 8171, Beyond the Finite: New Challenges in Verification and Semistructured Data (2008)

Abstract
From 20.04. to 25.04.2008, the Dagstuhl Seminar 08171 ``Beyond the Finite: New Challenges in Verification and Semistructured Data'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Anca Muscholl, Ramaswamy Ramanujam, Michaël Rusinowitch, Thomas Schwentick, and Victor Vianu. 08171 Abstracts Collection – Beyond the Finite: New Challenges in Verification and Semistructured Data. In Beyond the Finite: New Challenges in Verification and Semistructured Data. Dagstuhl Seminar Proceedings, Volume 8171, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{muscholl_et_al:DagSemProc.08171.1,
  author =	{Muscholl, Anca and Ramanujam, Ramaswamy and Rusinowitch, Micha\"{e}l and Schwentick, Thomas and Vianu, Victor},
  title =	{{08171 Abstracts Collection – Beyond the Finite: New Challenges in Verification and Semistructured Data}},
  booktitle =	{Beyond the Finite: New Challenges in Verification and Semistructured Data},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8171},
  editor =	{Anca Muscholl and Ramaswamy Ramanujam and Micha\"{e}l Rusinowitch and Thomas Schwentick and Victor Vianu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08171.1},
  URN =		{urn:nbn:de:0030-drops-15606},
  doi =		{10.4230/DagSemProc.08171.1},
  annote =	{Keywords: Infinite state systems, data values, verification, semistructured data}
}
Document
DOI: 10.4230/DagSemProc.08171.2
08171 Summary – Beyond the Finite: New Challenges in Verification and Semistructured Data

Authors: Anca Muscholl, Ramaswamy Ramanujam, Michaël Rusinowitch, Thomas Schwentick, and Victor Vianu

Published in: Dagstuhl Seminar Proceedings, Volume 8171, Beyond the Finite: New Challenges in Verification and Semistructured Data (2008)

Abstract
Exploring the interaction of model checking and database static analysis techniques in the development of novel approaches to the verification of software systems handling data.
Cite as

Anca Muscholl, Ramaswamy Ramanujam, Michaël Rusinowitch, Thomas Schwentick, and Victor Vianu. 08171 Summary – Beyond the Finite: New Challenges in Verification and Semistructured Data. In Beyond the Finite: New Challenges in Verification and Semistructured Data. Dagstuhl Seminar Proceedings, Volume 8171, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{muscholl_et_al:DagSemProc.08171.2,
  author =	{Muscholl, Anca and Ramanujam, Ramaswamy and Rusinowitch, Micha\"{e}l and Schwentick, Thomas and Vianu, Victor},
  title =	{{08171 Summary – Beyond the Finite: New Challenges in Verification and Semistructured Data}},
  booktitle =	{Beyond the Finite: New Challenges in Verification and Semistructured Data},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8171},
  editor =	{Anca Muscholl and Ramaswamy Ramanujam and Micha\"{e}l Rusinowitch and Thomas Schwentick and Victor Vianu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08171.2},
  URN =		{urn:nbn:de:0030-drops-15580},
  doi =		{10.4230/DagSemProc.08171.2},
  annote =	{Keywords: Infinite state systems, data values, verification, semistructured data}
}
Document
Abstract
DOI: 10.4230/LIPIcs.STACS.2008.1325
A Little Bit Infinite? On Adding Data to Finitely Labelled Structures (Abstract)

Authors: Thomas Schwentick

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
Finite or infinite strings or trees with labels from a finite alphabet play an important role in computer science. They can be used to model many interesting objects including system runs in Automated Verification and XML documents in Database Theory. They allow the application of formal tools like logical formulas to specify properties and automata for their implementation. In this framework, many reasoning tasks that are undecidable for general computational models can be solved algorithmically, sometimes even efficiently. Nevertheless, the use of finitely labelled structures usually requires an early abstraction from the real data. For example, theoretical research on XML processing very often con- centrates on the document structure (including labels) but ignores attribute or text values. While this abstraction has led to many interesting results, some aspects like key or other integrity constraints can not be adequately handled. In Automated Verification of software systems or communication protocols, infinite domains occur even more naturally, e.g., induced by program data, recursion, time, com- munication or by unbounded numbers of concurrent processes. Usually one approximates infinite domains by finite ones in a very early abstraction step. An alternative approach that has been investigated in recent years is to extend strings and trees by (a limited amount of) data and to use logical languages with a restricted ex- pressive power concerning this data. As an example, in the most simple setting, formulas can only test equality of data values. The driving goal is to identify logical languages and corresponding automata models which are strong enough to describe interesting proper- ties of data-enhanced structures while keeping decidability or even feasibility of automatic reasoning. The talk gives a basic introduction into data-enhanced finitely labelled structures, presents examples of their use, and highlights recent decidability and complexity results.
Cite as

Thomas Schwentick. A Little Bit Infinite? On Adding Data to Finitely Labelled Structures (Abstract). In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 17-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{schwentick:LIPIcs.STACS.2008.1325,
  author =	{Schwentick, Thomas},
  title =	{{A Little Bit Infinite?  On Adding Data to Finitely Labelled Structures}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{17--18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1325},
  URN =		{urn:nbn:de:0030-drops-13253},
  doi =		{10.4230/LIPIcs.STACS.2008.1325},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemProc.06451.1
06451 Abstracts Collection – Circuits, Logic, and Games

Authors: Thomas Schwentick, Denis Thérien, and Heribert Vollmer

Published in: Dagstuhl Seminar Proceedings, Volume 6451, Circuits, Logic, and Games (2007)

Abstract
From 08.11.06 to 10.11.06, the Dagstuhl Seminar 06451 ``Circuits, Logic, and Games'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Thomas Schwentick, Denis Thérien, and Heribert Vollmer. 06451 Abstracts Collection – Circuits, Logic, and Games. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{schwentick_et_al:DagSemProc.06451.1,
  author =	{Schwentick, Thomas and Th\'{e}rien, Denis and Vollmer, Heribert},
  title =	{{06451 Abstracts Collection – Circuits, Logic, and Games }},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6451},
  editor =	{Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.1},
  URN =		{urn:nbn:de:0030-drops-9785},
  doi =		{10.4230/DagSemProc.06451.1},
  annote =	{Keywords: Computational complexity theory, finite model theory, Boolean circuits, regular languages, finite monoids, Ehrenfeucht-Fra\backslash"\{\backslashi\}ss\backslash'\{e\} games}
}
Document
DOI: 10.4230/DagSemProc.06451.2
06451 Executive Summary – Circuits, Logic, and Games

Authors: Thomas Schwentick, Denis Thérien, and Heribert Vollmer

Published in: Dagstuhl Seminar Proceedings, Volume 6451, Circuits, Logic, and Games (2007)

Abstract
In this document we describe the original motivation and goals of the seminar as well as the sequence of talks given during the seminar.
Cite as

Thomas Schwentick, Denis Thérien, and Heribert Vollmer. 06451 Executive Summary – Circuits, Logic, and Games. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{schwentick_et_al:DagSemProc.06451.2,
  author =	{Schwentick, Thomas and Th\'{e}rien, Denis and Vollmer, Heribert},
  title =	{{06451 Executive Summary – Circuits, Logic, and Games }},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6451},
  editor =	{Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.2},
  URN =		{urn:nbn:de:0030-drops-9774},
  doi =		{10.4230/DagSemProc.06451.2},
  annote =	{Keywords: Circuits, Logics, Games}
}
Document
DOI: 10.4230/DagSemProc.05061.1
05061 Abstracts Collection – Foundations of Semistructured Data

Authors: Frank Neven, Thomas Schwentick, and Dan Suciu

Published in: Dagstuhl Seminar Proceedings, Volume 5061, Foundations of Semistructured Data (2005)

Abstract
From 06.02.05 to 11.02.05, the Dagstuhl Seminar 05061 ``Foundations of Semistructured Data'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Frank Neven, Thomas Schwentick, and Dan Suciu. 05061 Abstracts Collection – Foundations of Semistructured Data. In Foundations of Semistructured Data. Dagstuhl Seminar Proceedings, Volume 5061, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{neven_et_al:DagSemProc.05061.1,
  author =	{Neven, Frank and Schwentick, Thomas and Suciu, Dan},
  title =	{{05061 Abstracts Collection – Foundations of Semistructured Data}},
  booktitle =	{Foundations of Semistructured Data},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5061},
  editor =	{Frank Neven and Thomas Schwentick and Dan Suciu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05061.1},
  URN =		{urn:nbn:de:0030-drops-2330},
  doi =		{10.4230/DagSemProc.05061.1},
  annote =	{Keywords: Semistructured data, XML, database theory, document processing}
}
Document
DOI: 10.4230/DagSemProc.05061.2
05061 Summary – Foundations of Semi-structured Data

Authors: Frank Neven, Thomas Schwentick, and Dan Suciu

Published in: Dagstuhl Seminar Proceedings, Volume 5061, Foundations of Semistructured Data (2005)

Abstract
As in the first seminar on this topic, the aim o the workshop was to bring together people from the areas related to semi-structured data. However, besides the presentation of recent work, this time the main goal was to identify the main lines of a common framework for future foundational work on semi-structured data. These lines of research are summarized below. The workshop was of a very interdisciplinary nature with invitees from databases, structured documents, programming languages, information retrieval and formal language theory. Several of the lectures were presented by PhD students. We had four invited speakers and a panel on research evaluation. Due to strong connections between topics treated at this workshop, many of the participants initiated new cooperations and research projects.
Cite as

Frank Neven, Thomas Schwentick, and Dan Suciu. 05061 Summary – Foundations of Semi-structured Data. In Foundations of Semistructured Data. Dagstuhl Seminar Proceedings, Volume 5061, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{neven_et_al:DagSemProc.05061.2,
  author =	{Neven, Frank and Schwentick, Thomas and Suciu, Dan},
  title =	{{05061 Summary – Foundations of Semi-structured Data}},
  booktitle =	{Foundations of Semistructured Data},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5061},
  editor =	{Frank Neven and Thomas Schwentick and Dan Suciu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05061.2},
  URN =		{urn:nbn:de:0030-drops-2276},
  doi =		{10.4230/DagSemProc.05061.2},
  annote =	{Keywords: Report, summary}
}
Document
DOI: 10.4230/DagSemRep.318
Foundations of Semistructured Data (Dagstuhl Seminar 01361)

Authors: Alberto Mendelzon, Thomas Schwentick, and Dan Suciu

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Alberto Mendelzon, Thomas Schwentick, and Dan Suciu. Foundations of Semistructured Data (Dagstuhl Seminar 01361). Dagstuhl Seminar Report 318, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{mendelzon_et_al:DagSemRep.318,
  author =	{Mendelzon, Alberto and Schwentick, Thomas and Suciu, Dan},
  title =	{{Foundations of Semistructured Data (Dagstuhl Seminar 01361)}},
  pages =	{1--22},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{318},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.318},
  URN =		{urn:nbn:de:0030-drops-152026},
  doi =		{10.4230/DagSemRep.318},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact