The dynamic complexity of formal languages

DOI10.1145/2287718.2287719MaRDI QIDQ2946668zbMATH OpenOpenAlexFDO

Authors Wouter Gelade, Marcel Marquardt, Thomas Schwentick

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2009/1829/

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Formal languages and automata (68Q45)

Recommendations

• The dynamic complexity of formal languages
• Dynamic Complexity under Definable Changes
• Dynamic complexity theory revisited
• STACS 2005
• Dyn-FO: A parallel, dynamic complexity class

Cited in

(17)

• Work-sensitive dynamic complexity of formal languages
• Modern aspects of complexity within formal languages
• Dynamic conjunctive queries
• The dynamic descriptive complexity of k-clique
• On the quantifier-free dynamic complexity of reachability
• Dynamic complexity theory revisited
• The dynamic complexity of acyclic hypergraph homomorphisms
• Dynamic complexity of the Dyck reachability
• On formal languages in one-dimensional dynamical systems
• scientific article; zbMATH DE number 7471669 (Why is no real title available?)
• Dynamic algorithms for the Dyck languages
• A strategy for dynamic programs: start over and muddle through
• The dynamic complexity of formal languages
• A parallel algorithm for counting parse trees
• Query maintenance under batch changes with small-depth circuits
• Dynamic membership for regular languages
• Dynamic membership for regular tree languages

This page was built for publication: The dynamic complexity of formal languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946668)