Dynamic Complexity of Formal Languages

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Contains the material presenten at STACS 2009, extendes with proofs and examples which were omitted due lack of space

Scientific paper

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 using quantifier-free first-order updates, with and without auxiliary functions, respectively. It is shown that the languages maintainable in DynPROP exactly are the regular languages, even when allowing arbitrary precomputation. This enables lower bounds for DynPROP and separates DynPROP from DynQF and DynFO. Further, it is shown that any context-free language can be maintained in DynFO and a number of specific context-free languages, for example all Dyck-languages, are maintainable in DynQF. Furthermore, the dynamic complexity of regular tree languages is investigated and some results concerning arbitrary structures are obtained: there exist first-order definable properties which are not maintainable in DynPROP. On the other hand any existential first-order property can be maintained in DynQF when allowing precomputation.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Dynamic Complexity of Formal Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dynamic Complexity of Formal Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic Complexity of Formal Languages will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-527625

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.