2 citations · 2 across the 1 of their papers we have counts for
4 papers
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 of Reachability: How many changes can we handle?
Samir Datta, Pankaj Kumar, Anish Mukherjee +3
In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-order formulas after inserting or deleting single edges. Later, in 2018, this was exte…
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…
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…