77 citations · 281 across the 23 of their papers we have counts for
15 papers · 1 filter
Work-sensitive Dynamic Complexity of Formal Languages
Jonas Schmidt, Thomas Schwentick, Till Tantau +2
Which amount of parallel resources is needed for updating a query result after changing an input? In this work we study the amount of work required for dynamically answering member…
Dynamic Complexity Meets Parameterised Algorithms
Jonas Schmidt, Thomas Schwentick, Nils Vortmeier +2
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 formula…
Dynamic Conjunctive Queries
Thomas Zeume, Thomas Schwentick
The article investigates classes of queries maintainable by conjunctive queries (CQs) and their extensions and restrictions in the dynamic complexity framework of Patnaik and Immer…
A Strategy for Dynamic Programs: Start over and Muddle through
Samir Datta, Anish Mukherjee, Thomas Schwentick +2
In the setting of DynFO, dynamic programs update the stored result of a query whenever the underlying data changes. This update is expressed in terms of first-order logic. We intro…
Dynamic Complexity under Definable Changes
Thomas Schwentick, Nils Vortmeier, Thomas Zeume
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 fir…
Static Analysis for Logic-Based Dynamic Programs
Thomas Schwentick, Nils Vortmeier, Thomas Zeume
A dynamic program, as introduced by Patnaik and Immerman (1994), maintains the result of a fixed query for an input database which is subject to tuple insertions and deletions. It…
Reachability is in DynFO
Samir Datta, Raghav Kulkarni, Anish Mukherjee +2
Patnaik and Immerman introduced the dynamic complexity class DynFO of database queries that can be maintained by first-order dynamic programs with the help of auxiliary relations u…
A Short Note on Two-Variable Logic with a Linear Order Successor and a Preorder Successor
Amaldev Manuel, Thomas Schwentick, Thomas Zeume
The finite satisfiability problem of two-variable logic extended by a linear order successor and a preorder successor is shown to be undecidable.
On the quantifier-free dynamic complexity of Reachability
Thomas Zeume, Thomas Schwentick
The dynamic complexity of the reachability query is studied in the dynamic complexity framework of Patnaik and Immerman, restricted to quantifier-free update formulas. It is shown…
A note on the expressive power of linear orders
Thomas Schwentick, Nicole Schweikardt
This article shows that there exist two particular linear orders such that first-order logic with these two linear orders has the same expressive power as first-order logic with th…
Two-Variable Logic with Two Order Relations
Thomas Schwentick, Thomas Zeume
It is shown that the finite satisfiability problem for two-variable logic over structures with one total preorder relation, its induced successor relation, one linear order relatio…
Temporal Logics on Words with Multiple Data Values
Ahmet Kara, Thomas Schwentick, Thomas Zeume
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…
On the Hybrid Extension of CTL and CTL+
Ahmet Kara, Martin Lange, Thomas Schwentick +1
The paper studies the expressivity, relative succinctness and complexity of satisfiability for hybrid extensions of the branching-time logics CTL and CTL+ by variables. Previous co…
Complexity of Hybrid Logics over Transitive Frames
Martin Mundhenk, Thomas Schneider, Thomas Schwentick +1
This paper examines the complexity of hybrid logics over transitive frames, transitive trees, and linear frames. We show that satisfiability over transitive frames for the hybrid l…
Solving equations in the relational algebra
Joachim Biskup, Jan Paredaens, Thomas Schwentick +1
Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yie…