77 citations · 281 across the 23 of their papers we have counts for
Showing 2008Show all
2 papers · 1 filter
cs.CC2008
Dynamic Complexity of Formal Languages
Wouter Gelade, Marcel Marquardt, Thomas Schwentick
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 us…
cs.LO2008
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…