Incremental recomputation in local languages.

DOI10.1016/S0890-5401(03)00017-8zbMath1054.68085OpenAlexW2045841926WikidataQ61910881 ScholiaQ61910881MaRDI QIDQ1401928

Guozhu Dong, Limsoon Wong, Leonid O. Libkin

Publication date: 19 August 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00017-8

zbMATH Keywords

SQLTransitive closureLocalityFirst-order logicIncremental recomputation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

Dynamic conjunctive queries ⋮ The dynamic descriptive complexity of \(k\)-clique ⋮ A Top-Down Query Answering Procedure for Normal Logic Programs Under the Any-World Assumption ⋮ On the quantifier-free dynamic complexity of reachability ⋮ Approximate well-founded semantics, query answering and generalized normal logic programs over lattices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Principles of programming with complex objects and collection types
• Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
• Complexity models for incremental computation
• Deterministic FOIES are strictly weaker
• Dyn-FO: A parallel, dynamic complexity class
• Query languages for bags and aggregate functions
• On monadic NP vs monadic co-NP
• Incremental and decremental evaluation of transitive closure by first- order queries
• Languages that Capture Complexity Classes
• Notions of locality and their logical characterizations over finite models
• Logics with aggregate operators
• Locality of order-invariant first-order formulas

This page was built for publication: Incremental recomputation in local languages.