Preservation and decomposition theorems for bounded degree structures

DOI10.2168/LMCS-11(4:17)2015MaRDI QIDQ3460422zbMATH OpenFDO

Authors Frederik Harwath, Lucas Heimberg, Nicole Schweikardt

Publication date 7 January 2016

Published in Logical Methods in Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational logicfirst-order logichomomorphism preservationpreservation theoremsHanf localityFeferman-Vaughtelementary algorithmsexistential preservationLoś-Tarskimodulo counting quantifiersstructures of bounded degree

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Descriptive complexity and finite models (68Q19) Interpolation, preservation, definability (03C40)

Recommendations

• Preservation and decomposition theorems for bounded degree structures
• An Optimal Gaifman Normal Form Construction for Structures of Bounded Degree
• Model Theory Makes Formulas Large
• Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree
• Automatic structures of bounded degree

Cited in

(5)

• Gaifman normal forms for counting extensions of first-order logic
• Preservation and decomposition theorems for bounded degree structures
• Feferman-vaught decompositions for prefix classes of first order logic
• When locality meets preservation
• Model Theory Makes Formulas Large

This page was built for publication: Preservation and decomposition theorems for bounded degree structures

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