8 citations · 8 across the 3 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.CC2008★ 8 cited
Succinctness of the Complement and Intersection of Regular Expressions
Wouter Gelade, Frank Neven
We study the succinctness of the complement and intersection of regular expressions. In particular, we show that when constructing a regular expression defining the complement of a…