77 citations · 281 across the 23 of their papers we have counts for
Showing cs.CCShow 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.CC1998★ 45 cited
The descriptive complexity approach to LOGCFL
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick +1
Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses o…