scientific article; zbMATH DE number 7056236

zbMath1421.68014arXiv1704.07998MaRDI QIDQ5376663

Thomas Zeume, Nils Vortmeier, Samir Datta, Anish Mukherjee, Thomas Schwentick

Publication date: 17 May 2019

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

monadic second-order logictreewidthdynamics complexity

Mathematics Subject Classification ID

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

Related Items

The dynamic complexity of acyclic hypergraph homomorphisms ⋮ Unnamed Item ⋮ Dynamic complexity of expansion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic uses of the Feferman-Vaught theorem
• Elements of finite model theory.
• The monadic theory of order
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Dyn-FO: A parallel, dynamic complexity class
• Nonrecursive incremental evaluation of Datalog queries
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Dynamic complexity theory revisited
• The dynamic complexity of formal languages
• Dynamic Complexity under Definable Changes
• Reachability is in DynFO
• Reachability Is in DynFO
• Where First-Order and Monadic Second-Order Logic Coincide