Automatic structures of bounded degree revisited

DOI10.2178/jsl/1318338854zbMath1272.03148OpenAlexW2570921773MaRDI QIDQ3107359

Markus Lohrey, Dietrich Kuske

Publication date: 23 December 2011

Published in: The 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 theorytree automatic structurestring automatic structurestructure of bounded degree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) 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) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items

An optimal construction of Hanf sentences ⋮ Observation and distinction: representing information in infinite games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tree-Automatic Well-Founded Trees ⋮ Uniformly Automatic Classes of Finite Structures ⋮ Automatic Structures of Bounded Degree Revisited ⋮ The isomorphism problem on classes of automatic structures with transitive relations

Cites Work

• Unnamed Item
• Single-valuedness of tree transducers is decidable in polynomial time
• A uniform method for proving lower bounds on the computational complexity of logical theories
• On direct products of automaton decidable theories
• Definable relations and first-order query languages over strings
• Automata Presenting Structures: A Survey of the Finite String Case
• Alternation
• First-order and counting theories ofω-automatic structures