Model Theory Makes Formulas Large

DOI10.1007/978-3-540-73420-8_78MaRDI QIDQ5428869zbMATH OpenOpenAlexWikidataFDO

Authors Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt

Publication date 28 November 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73420-8_78

Mathematics Subject Classification ID

Basic properties of first-order languages and structures (03C07) Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Preservation and decomposition theorems for bounded degree structures
• Preservation and decomposition theorems for bounded degree structures
• Notions of locality and their logical characterizations over finite models
• Shrinking games and local formulas
• Locality from circuit lower bounds

Cited in

(19)

• There is no recursive link between the k-size of a model and its cardinality
• The uniform measure of simple regular sets of infinite trees
• Preservation and decomposition theorems for bounded degree structures
• An optimal construction of Hanf sentences
• Stretchings
• The compositional method and regular reachability
• Gaifman normal forms for counting extensions of first-order logic
• Enumerating answers to first-order queries over databases of low degree
• Compositional failure detection in structured transition systems
• Effective interpolation and preservation in guarded logics
• The Complexity of Decomposing Modal and First-Order Theories
• Feferman-vaught decompositions for prefix classes of first order logic
• Forbidden induced subgraphs and the Łoś-Tarski theorem
• Extensions and limits of the Specker-Blatter theorem
• When locality meets preservation
• Extensions and limits of the Specker-Blatter theorem
• Elementary first-order model checking for sparse graphs
• The parameterized complexity of k-edge induced subgraphs
• A generalization of the Łoś-Tarski preservation theorem

This page was built for publication: Model Theory Makes Formulas Large

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