77 citations · 281 across the 23 of their papers we have counts for
32 papers
On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages
Jonas Schmidt, Thomas Schwentick, Jennifer Todtenhoefer
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…
Dynamic constant time parallel graph algorithms with sub-linear work
Jonas Schmidt, Thomas Schwentick
The paper proposes dynamic parallel algorithms for connectivity and bipartiteness of undirected graphs that require constant time and work on the CRCW PRAM model. Th…
Work-Efficient Query Evaluation in Constant Time with PRAMs
Jens Keppeler, Thomas Schwentick, Christopher Spinrath
The article studies query evaluation in parallel constant time in the CRCW PRAM model. While it is well-known that all relational algebra queries can be evaluated in constant time…
Low-Latency Sliding Window Algorithms for Formal Languages
Moses Ganardi, Louis Jachiet, Markus Lohrey +1
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…
Rewriting with Acyclic Queries: Mind Your Head
Gaetano Geck, Jens Keppeler, Thomas Schwentick +1
The paper studies the rewriting problem, that is, the decision problem whether, for a given conjunctive query and a set of views, there is a conjunctive query $Q'…
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…