Dynamic Complexity under Definable Changes

DOI10.4230/LIPICS.ICDT.2017.19MaRDI QIDQ3174912zbMATH OpenOpenAlexFDO

Authors Thomas Schwentick, Nils Vortmeier, Thomas Zeume

Publication date 18 July 2018

Full work available at URL https://arxiv.org/abs/1701.02494

zbMATH Keywords

dynamic programsdynamic descriptive complexitySQL updates

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Database theory (68P15) Logic in computer science (03B70) Descriptive complexity and finite models (68Q19)

Abstract: This paper studies dynamic complexity under definable change operations in the DynFO framework by Patnaik and Immerman. It is shown that for changes definable by parameter-free first-order formulas, all (uniform) $A{C}^1$ queries can be maintained by first-order dynamic programs. Furthermore, many maintenance results for single-tuple changes are extended to more powerful change operations: (1) The reachability query for undirected graphs is first-order maintainable under single tuple changes and first-order defined insertions, likewise the reachability query for directed acyclic graphs under quantifier-free insertions. (2) Context-free languages are first-order maintainable under $Sigm{a}_1$-defined changes. These results are complemented by several inexpressibility results, for example, that the reachability query cannot be maintained by quantifier-free programs under definable, quantifier-free deletions.

Recommendations

• Dynamic complexity under definable changes
• Dynamic complexity theory revisited
• STACS 2005
• Dynamic complexity of the Dyck reachability
• Complexity in dynamics and computation
• Coarse-Grained Complexity for Dynamic Algorithms
• Symbolic dynamics and characterization of complexity

Cited in

(14)

• Dynamic conjunctive queries
• Dynamic complexity of expansion
• Dynamic complexity of the Dyck reachability
• A strategy for dynamic programs: start over and muddle through
• Reachability and distances under multiple changes
• Work-sensitive dynamic complexity of formal languages
• The dynamic complexity of formal languages
• Dynamic complexity theory revisited
• STACS 2005
• The dynamic complexity of acyclic hypergraph homomorphisms
• The dynamic complexity of formal languages
• Small dynamic complexity classes. An investigation into dynamic descriptive complexity
• Dynamic complexity under definable changes
• Action complexity in the presence of defects and boundaries

This page was built for publication: Dynamic Complexity under Definable Changes

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