Automatic Structures of Bounded Degree Revisited

DOI10.1007/978-3-642-04027-6_27MaRDI QIDQ3644760zbMATH OpenOpenAlexFDO

Authors Markus Lohrey, Dietrich Kuske

Publication date 12 November 2009

Published in Computer Science Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-04027-6_27

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Automatic structures of bounded degree
• Automatic structures of bounded degree revisited
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Theories of Automatic Structures and Their Complexity
• Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree

Cites work

• A uniform method for proving lower bounds on the computational complexity of logical theories
• Automata Presenting Structures: A Survey of the Finite String Case
• Automatic structures of bounded degree
• Automatic structures of bounded degree revisited
• Cardinality and counting quantifiers on omega-automatic structures
• Decision Problems of Finite Automata Design and Related Arithmetics
• First-order and counting theories ofω-automatic structures
• scientific article; zbMATH DE number 2038749 (Why is no real title available?)
• On decidability properties of one-dimensional cellular automata
• On direct products of automaton decidable theories
• On the valuedness of finite transducers
• STACS 2004

Cited in

(10)

• Constructing decidable graphs from decidable structures
• Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree
• Size and computation of injective tree automatic presentations
• Automatic structures of bounded degree revisited
• Automatic structures of bounded degree
• Theories of Automatic Structures and Their Complexity
• EQUIVALENT AUTOMATIC STRUCTURES AND THEIR BOUNDARIES
• Automatic structures: twenty years later
• An Optimal Gaifman Normal Form Construction for Structures of Bounded Degree
• Ehrenfeucht-Fraïssé goes automatic for real addition

This page was built for publication: Automatic Structures of Bounded Degree Revisited

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