Some natural decision problems in automatic graphs

DOI10.2178/jsl/1268917499zbMath1192.03010OpenAlexW1999471820MaRDI QIDQ3570167

Markus Lohrey, Dietrich Kuske

Publication date: 24 June 2010

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

Full work available at URL: https://semanticscholar.org/paper/7281ea1645e427bf3389937113a5c3f47e551ed5

zbMATH Keywords

computational complexityrecursive graphsautomatic graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Computable structure theory, computable model theory (03C57)

Related Items

Sequential Relational Decomposition ⋮ Unnamed Item ⋮ Where Automatic Structures Benefit from Weighted Automata ⋮ The isomorphism problem on classes of automatic structures with transitive relations

Cites Work

• Unnamed Item
• Hamiltonian paths in infinite graphs
• Finite presentations of infinite structures: Automata and interpretations
• Taking it to the limit: On infinite variants of NP-complete problems
• Automatic graphs and D0L-sequences of finite graphs
• Automata Presenting Structures: A Survey of the Finite String Case
• The Planar Hamiltonian Circuit Problem is NP-Complete
• LICS 2001 special issue
• Automatic linear orders and trees
• Logical Reversibility of Computation
• ÜBER Euler‐Linien Unendlicher Graphen

This page was built for publication: Some natural decision problems in automatic graphs