A strategy for dynamic programs: start over and muddle through

MaRDI QIDQ5376663zbMATH OpenFDO

Authors Samir Datta, A. Mukherjee, Thomas Schwentick, Nils Vortmeier, Thomas Zeume

Publication date 17 May 2019

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

zbMATH Keywords

dynamics complexitymonadic second-order logictreewidth

Mathematics Subject Classification ID

Logic in computer science (03B70) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A strategy for dynamic programs: start over and muddle through
• Dynamic complexity under definable changes
• Static analysis for logic-based dynamic programs
• STACS 2005
• Dyn-FO: A parallel, dynamic complexity class

Cites work

• A strategy for dynamic programs: start over and muddle through
• Algorithmic uses of the Feferman-Vaught theorem
• Dyn-FO: A parallel, dynamic complexity class
• Dynamic complexity theory revisited
• Dynamic Complexity under Definable Changes
• Elements of finite model theory.
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• Logical theories and compatible operations
• Nonrecursive incremental evaluation of Datalog queries
• Reachability and distances under multiple changes
• Reachability is in DynFO
• Reachability is in DynFO
• The dynamic complexity of formal languages
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic theory of order
• Where first-order and monadic second-order logic coincide

Cited in

(7)

• Dynamic complexity of expansion
• The dynamic complexity of acyclic hypergraph homomorphisms
• A strategy for dynamic programs: start over and muddle through
• Static analysis for logic-based dynamic programs
• A strategy for dynamic programs: start over and muddle through
• Dynamic complexity of reachability: how many changes can we handle?
• The parallel dynamic complexity of the abelian Cayley group membership problem

This page was built for publication: A strategy for dynamic programs: start over and muddle through

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