Automatic structures of bounded degree revisited

DOI10.2178/JSL/1318338854MaRDI QIDQ3107359zbMATH OpenOpenAlexFDO

Authors Markus Lohrey, Dietrich Kuske

Publication date 23 December 2011

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.244.2221

zbMATH Keywords

computational complexitydecidable theorystring automatic structurestructure of bounded degreetree automatic structure

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Computable structure theory, computable model theory (03C57) Automata and formal grammars in connection with logical questions (03D05) Theory of numerations, effectively presented structures (03D45) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Automatic Structures of Bounded Degree Revisited
• Automatic structures of bounded degree
• EQUIVALENT AUTOMATIC STRUCTURES AND THEIR BOUNDARIES
• Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree
• Automated bounds on recursive structures
• Uniformly Automatic Classes of Finite Structures
• STACS 2004
• Model-theoretic complexity of automatic structures
• Model Theoretic Complexity of Automatic Structures (Extended Abstract)

Cites work

• A uniform method for proving lower bounds on the computational complexity of logical theories
• Alternation
• Automata Presenting Structures: A Survey of the Finite String Case
• Definable relations and first-order query languages over strings
• First-order and counting theories ofω-automatic structures
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• On direct products of automaton decidable theories
• Single-valuedness of tree transducers is decidable in polynomial time

Cited in

(17)

• Observation and distinction: representing information in infinite games
• The isomorphism problem on classes of automatic structures with transitive relations
• Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree
• Size and computation of injective tree automatic presentations
• Automatic structures of bounded degree
• Theories of Automatic Structures and Their Complexity
• Automatic Structures of Bounded Degree Revisited
• EQUIVALENT AUTOMATIC STRUCTURES AND THEIR BOUNDARIES
• An optimal construction of Hanf sentences
• Climbing up the elementary complexity classes with theories of automatic structures
• The Cayley-graph of the queue monoid: logic and decidability
• Uniformly Automatic Classes of Finite Structures
• An Optimal Gaifman Normal Form Construction for Structures of Bounded Degree
• Tree-automatic well-founded trees
• Foundations of Software Science and Computation Structures
• Universal quantification makes automatic structures hard to decide
• Universal quantification makes automatic structures hard to decide

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 Q3107359)