The Dynamic complexity of formal languages

Abstract : 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.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.481-492, 2009
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00359755
Contributeur : Publications Loria <>
Soumis le : lundi 9 février 2009 - 12:11:36
Dernière modification le : vendredi 13 février 2009 - 12:26:40
Document(s) archivé(s) le : mardi 8 juin 2010 - 22:06:00

Fichier

40-gelade.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00359755, version 1

Collections

Citation

Wouter Gelade, Marcel Marquardt, Thomas Schwentick. The Dynamic complexity of formal languages. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.481-492, 2009. 〈inria-00359755〉

Partager

Métriques

Consultations de la notice

105

Téléchargements de fichiers

119