Some natural decision problems in automatic graphs
Copyright policy )Some natural decision problems in automatic graphs
AbstractFor automatic and recursive graphs, we investigate the following problems:(A) existence of a Hamiltonian path and existence of an infinite path in a tree(B) existence of an Euler path, bounding the number of ends, and bounding the number of infinite branches in a tree(C) existence of an infinite clique and an infinite version of set coverThe complexity of these problems is determined for automatic graphs and. supplementing results from the literature, for recursive graphs. Our results show that these problems(A) are equally complex for automatic and for recursive graphs (-complete).(B) are moderately less complex for automatic than for recursive graphs (complete for different levels of the arithmetic hierarchy),(C) are much simpler for automatic than for recursive graphs (decidable and -complete, resp.).
- University of Bordeaux France
- French National Centre for Scientific Research France
- Laboratoire Bordelais de Recherche en Informatique France
- University of Bordeaux France
- Leipzig University Germany
Complexity of computation (including implicit computational complexity), computational complexity, Analysis of algorithms and problem complexity, recursive graphs, Computable structure theory, computable model theory, automatic graphs, Automata and formal grammars in connection with logical questions, Decidability of theories and sets of sentences, Graph theory (including graph drawing) in computer science, Paths and cycles
Complexity of computation (including implicit computational complexity), computational complexity, Analysis of algorithms and problem complexity, recursive graphs, Computable structure theory, computable model theory, automatic graphs, Automata and formal grammars in connection with logical questions, Decidability of theories and sets of sentences, Graph theory (including graph drawing) in computer science, Paths and cycles
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).11 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!