Some natural decision problems in automatic graphs

DOI10.2178/JSL/1268917499MaRDI QIDQ3570167zbMATH OpenOpenAlexFDO

Authors Markus Lohrey, Dietrich Kuske

Publication date 24 June 2010

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

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

zbMATH Keywords

automatic graphscomputational complexityrecursive graphs

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) Complexity of computation (including implicit computational complexity) (03D15) Paths and cycles (05C38) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1759440
• A note on decision versus search for graph automorphism
• scientific article; zbMATH DE number 5041651
• On automatic transitive graphs
• Unary automatic graphs: an algorithmic perspective
• Unary Automatic Graphs: An Algorithmic Perspective
• scientific article; zbMATH DE number 3499653
• scientific article; zbMATH DE number 7604432
• scientific article; zbMATH DE number 4053563
• scientific article; zbMATH DE number 4101136

Cites work

• Automata Presenting Structures: A Survey of the Finite String Case
• Automatic graphs and D0L-sequences of finite graphs
• Automatic linear orders and trees
• Finite presentations of infinite structures: Automata and interpretations
• Hamiltonian paths in infinite graphs
• scientific article; zbMATH DE number 41228 (Why is no real title available?)
• LICS 2001 special issue
• Logical Reversibility of Computation
• Taking it to the limit: On infinite variants of NP-complete problems
• The Planar Hamiltonian Circuit Problem is NP-Complete
• ÜBER Euler‐Linien Unendlicher Graphen

Cited in

(14)

• Hamiltonian paths in infinite graphs
• The isomorphism problem on classes of automatic structures with transitive relations
• Where automatic structures benefit from weighted automata
• Typical paths of a graph
• Unary Automatic Graphs: An Algorithmic Perspective
• Unary automatic graphs: an algorithmic perspective
• scientific article; zbMATH DE number 1759440 (Why is no real title available?)
• Climbing up the elementary complexity classes with theories of automatic structures
• Ramsey quantifiers over automatic structures: complexity and applications to verification
• Simple classes of automatic structures
• The theory of reachability of trace-pushdown systems
• Paths, ends and the separation problem for infinite graphs
• The algebras for automatic relations
• Karp's NP-complete problems over first-order definable structures

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

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