Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T10:56:23.406Z Has data issue: false hasContentIssue false
  • English
  • Français

Some natural decision problems in automatic graphs

Published online by Cambridge University Press:  12 March 2014

Dietrich Kuske  and
Markus Lohrey
Dietrich Kuske
Affiliation:
Labri, CNRS, Université Bordeaux I, 351, Cours de la Libération F-33405 Talence, France. E-mail: [email protected]
Markus Lohrey
Affiliation:
Universität Leipzig, Institut für Informatik Postfach 100920, D-04009 Leipzig, Germany. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

For 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 cover

The 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.).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 75 , Issue 2 , June 2010 , pp. 678 - 710
Copyright
Copyright © Association for Symbolic Logic 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Bárány, V., Kaiser, Ł., and Rubin, S., Cardinality and counting quantifiers on omega-automatic structures, STACS2008, IFIB Schloss Dagstuhl, 2008, pp. 385–396.Google Scholar
[2]Bean, D. R., Effective coloration, this Journal, .vol. 41 (1976), no. 2, pp. 469–480.Google Scholar
[3]Bean, D. R., Recursive Euler and Hamilton paths, Proceedings of the American Mathematical Society, vol. 55 (1976), no. 2, pp. 385–394.CrossRefGoogle Scholar
[4]Bennett, C. H., Logical reversibility of computation, IBM Journal of Research and Development, vol. 17 (1973), pp. 525–532.CrossRefGoogle Scholar
[5]Berger, R., The undecidability of the domino problem, Memoirs of the American Mathematical Society, (1966), no. 66, p. 72.Google Scholar
[6]Blumensath, A., Automatic structures, Technical report, RWTH Aachen, 1999.Google Scholar
[7]Blumensath, A. and Grädel, E., Automatic structures, LICS 2000, IEEE Computer Society Press, 2000, pp. 51–62.Google Scholar
[8]Blumensath, A. and Grädel, E., Finite presentations of infinite structures: Automata and interpretations, Theory of Computing Systems, vol. 37 (2004), no. 6, pp. 641–674.CrossRefGoogle Scholar
[9]Dicks, W. and Dunwoody, M. J., Groups acting on graphs, Cambridge University Press, 1989.Google Scholar
[10]Diestel, R., Graph theory, third ed., Springer, 2006.Google Scholar
[11]Erdös, P., Grünwald, T., and Vazsonyi, E., Über Euler–Linien unendlicher Graphen, Journal of Mathematics and Physics, vol. 17 (1938), no. 2, pp. 59–75.CrossRefGoogle Scholar
[12]Euler, L., Solutii problematis ad geometriam situs pertinentis, Commentarii Academiae Scientiarum Petropolitanae, vol. 8 (1736), pp. 128–140.Google Scholar
[13]Garey, M. R., Johnson, D. S., and Tarjan, R. E., The planar Hamiltonian circuit problem is NP-complete, SIAM Journal on Computing, vol. 5 (1976), no. 4, pp. 704–714.CrossRefGoogle Scholar
[14]Gasarch, W., A survey of recursive combinatorics, Handbook of recursive mathematics (Ershov, Yu. L., Goncharov, S. S., Marek, V. W., Nerode, A., and Remmel, J., editors), vol. 2, Studies in Logic and the Foundations of Mathematics, no. 139, Elsevier, 1998, pp. 1041–1176.Google Scholar
[15]Harel, D., A simple undecidable domino problem (or, a lemma on infinite trees, with applications), Proceedings of the Logic and Computation Conference, Clayton, 1984.Google Scholar
[16]Harel, D., Recurring dominoes: making the highly undecidable highly understandable, Annals of Discrete Mathematics, vol. 24 (1985), pp. 51–72.Google Scholar
[17]Harel, D., Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness, Journal of the Association for Computing Machinery, vol. 33 (1986), no. 1, pp. 224–248.CrossRefGoogle Scholar
[18]Harel, D., Hamiltonian paths in infinite graphs, Israel Journal of Mathematics, vol. 76 (1991), no. 3, pp. 317–336.CrossRefGoogle Scholar
[19]Hirst, T. and Harel, D., Taking it to the limit: on infinite variants of NP-complete problems, Journal of Computer and System Sciences, vol. 53 (1996), pp. 180–193.CrossRefGoogle Scholar
[20]Khoussainov, B. and Minnes, M., Model theoretic complexity of automatic structures, TAMC 2008, Lecture Notes in Computer Science, no. 4978, Springer, 2008, pp. 514–525.Google Scholar
[21]Khoussainov, B. and Nerode, A., Automatic presentations of structures, LCC: International Workshop on Logic and Computational Complexity, Lecture Notes in Computer Science, no. 960, 1995, pp. 367–392.CrossRefGoogle Scholar
[22]Khoussainov, B., Nies, A., Rubin, S., and Stephan, F., Automatic structures: richness and limitations. Logical Methods in Computer Science, vol. 3 (2007), no. 2, 2:2, 18 pp. (electronic).Google Scholar
[23]Khoussainov, B., Rubin, S., and Stephan, F., Automatic partial orders, LICS 2003, IEEE Computer Society Press, 2003, pp. 168–177.Google Scholar
[24]Khoussainov, B., Rubin, S., and Stephan, F., Definability and regularity in automatic structures, STACS 2004, Lecture Notes in Computer Science, no. 2996, Springer, 2004, pp. 440–451.CrossRefGoogle Scholar
[25]Khoussainov, B., Rubin, S., and Stephan, F., Automatic linear orders and trees, ACM Transactions on Computational Logic, vol. 6 (2005), no. 4, pp. 675–700.CrossRefGoogle Scholar
[26]Kleene, S. C., Recursive predicates and quantifiers, Transactions of the American Mathematical Society, vol. 53 (1943), pp. 41–73.CrossRefGoogle Scholar
[27]Kozen, D., Theory of Computation, Springer, 2006.Google Scholar
[28]Kuske, D. and Lohrey, M., Euler paths and ends in automatic and recursive graphs, AFL 2008, Hungarian Academy of Sciences, 2008, pp. 245–256.Google Scholar
[29]Kuske, D. and Lohrey, M., First-order and counting theories of co-automatic structures, this Journal, vol. 73 (2008), pp. 129–150.Google Scholar
[30]Kuske, D. and Lohrey, M., Hamiltonicity of automatic graphs, IFIP-TCS 2008, Springer, 2008, pp. 445–459.Google Scholar
[31]Ly, O., Automatic graphs and D0L-sequences of finite graphs, Journal of Computer and System Sciences, vol. 67 (2003), no. 3, pp. 497–545.CrossRefGoogle Scholar
[32]Manaster, A. B. and Rosenstein, J. G., Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall), Proceedings of the London Mathematical Society, vol. 25 (1972), pp. 615–654.CrossRefGoogle Scholar
[33]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, 1968.Google Scholar
[34]Rubin, S., Automatic structures, Ph.D. thesis, University of Auckland, 2004.Google Scholar
[35]Rubin, S., Automata presenting structures: A survey of the finite string case, The Bulletin of Symbolic Logic, vol. 14 (2008), pp. 169–209.CrossRefGoogle Scholar
[36]Thomas, W., A short introduction to infinite automata, DLT 2001, Lecture Notes in Computer Science, no. 2295, Springer, 2001, pp. 130–144.Google Scholar
[37]Wang, H., Proving theorems by pattern recognition, Bell Systems Technilogical Journal, vol. 40 (1961), pp. 1–41.CrossRefGoogle Scholar