Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree

DOI10.4230/LIPICS.STACS.2012.242MaRDI QIDQ2904765zbMATH OpenFDO

Authors Antoine Durand-Gasselin, Peter Habermehl

Publication date 23 August 2012

zbMATH Keywords

complexityautomatic structuresautomata-based decision procedures for logical theoriesEhrenfeucht-Fraïssé games

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Computable structure theory, computable model theory (03C57)

Recommendations

• Automatic structures of bounded degree
• Automatic Structures of Bounded Degree Revisited
• Automatic structures of bounded degree revisited
• Foundations of Software Science and Computation Structures
• Ehrenfeucht-Fraïssé goes automatic for real addition

Cited in

(11)

• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Automatic structures of bounded degree
• Preservation and decomposition theorems for bounded degree structures
• Ehrenfeucht-Fraïssé goes automatic for real addition
• Ehrenfeucht-Fraïssé goes automatic for real addition
• Isomorphisms of scattered automatic linear orders
• The isomorphism problem on classes of automatic structures with transitive relations
• Uniformly Automatic Classes of Finite Structures
• Geometric decision procedures and the VC dimension of linear arithmetic theories
• Automatic structures of bounded degree revisited
• Automatic Structures of Bounded Degree Revisited

This page was built for publication: Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree

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