Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-21T18:23:16.288Z Has data issue: false hasContentIssue false
  • English
  • Français

Automata Presenting Structures: A Survey of the Finite String Case

Published online by Cambridge University Press:  15 January 2014

Sasha Rubin
Sasha Rubin*
Affiliation:
Department of Computer Science, University of Auckland, New ZealandE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A structure has a (finite-string) automatic presentation if the elements of its domain can be named by finite strings in such a way that the coded domain and the coded atomic operations are recognised by synchronous multitape automata. Consequently, every structure with an automatic presentation has a decidable first-order theory. The problems surveyed here include the classification of classes of structures with automatic presentations, the complexity of the isomorphism problem, and the relationship between definability and recognisability.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 14 , Issue 2 , June 2008 , pp. 169 - 209
Copyright
Copyright © Association for Symbolic Logic 2008

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] Ash, C. J. and Nerode, A., Intrinsically recursive relations, Aspects of effective algebra (clayton, 1979), Upside Down A Book Co., Yarra Glen, 1981, pp. 26–41.Google Scholar
[2] Bárány, V., Invariants of automatic presentations and semi-synchronous transductions, STACS 2006 (Durand, B. and Thomas, W., editors), Lecture Notes in Computer Science, vol. 3884, Springer, 2006, pp. 289–300.Google Scholar
[3] Bárány, V. Automatic presentations of infinite structures, Ph.D. thesis, RWTH Aachen, 2007.Google Scholar
[4] Bárány, V., Kaiser, L., and Rubin, S., Countable omega-automatic structures and their presentations, STACS 2008 (Albers, S., Weil, P., and Rochange, C., editors), Dagstuhl Seminar Proceedings, vol. 08001, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, 2008.Google Scholar
[5] Benedikt, M. and Libkin, L., Tree extension algebras: logics, automata, and query languages, LICS 2002, IEEE Computer Society, 2002, pp. 203–212.Google Scholar
[6] Benedikt, M., Libkin, L., Schwentick, T., and Segoufin, L., A model-theoretic approach to regular string relations, LICS 2001, IEEE Computer Society, 2001, pp. 431–440.Google Scholar
[7] Bennett, C. H., Logical reversibility of computation, IBM Journal of Research and Development, vol. 17 (1973), no. 6, pp. 525–532.Google Scholar
[8] Berstel, Jean, Transductions and Context-Free languages, Leitfáden der Angewandten Mathematik und Mechanik [Guides to Applied Mathematics and Mechanics], vol. 38, B. G. Teubner, Stuttgart, 1979.CrossRefGoogle Scholar
[9] Blumensath, A., Automatic structures, Diploma thesis, Rwth Aachen, 1999.Google Scholar
[10] Prefix-recognisable graphs and monadic second-order logic, Technical report, RWTH Aachen, 2001.Google Scholar
[11] Axiomatising tree-interpretable structures, STACS 2002 (Alt, H. and Ferreira, A., editors), Lecture Notes in Computer Science, vol. 2285, Springer, 2002, pp. 596–607.Google Scholar
[12] Blumensath, A. and Grádel, E., Automatic structures, LICS 2000, IEEE Computer Society, 2000, pp. 51–62.Google Scholar
[13] Blumensath, A. Finite presentations of infinite structures: Automata and interpretations, Proceedings of the 2nd International Workshop on Complexity in Automated Deduction, CiAD 2002, 2002.Google Scholar
[14] Blumensath, A. Finite presentations of infinite structures: Automata and interpretations, Theory of Computing Systems, vol. 37 (2004), pp. 641–674.Google Scholar
[15] Bruyère, V., Hansel, G., Christian, C. Michaux, and Villemaire, R., Logic and p-recognizable sets of integers, Bulletin of the Belgian Mathematical Society. Simon Stevin, vol. 1 (1994), no. 2, pp. 191–238, Journées Montoises (Mons, 1992).Google Scholar
[16] Büchi, J. R., Weak second-order arithmetic and finite automata, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 6 (1960), pp. 66–92.Google Scholar
[17] Büchi, J. R. On a decision method in restricted second order arithmetic, Logic, methodology and philosophy of science, Stanford University Press, 1962, pp. 1–11.Google Scholar
[18] Cannon, J. W., The combinatorial structure of cocompact discrete hyperbolic groups, Geometriae Dedicata (Historical Archive), Vol. 16 (1984), No. 2, Pp. 123–148.Google Scholar
[19] Cannon, J. W., Epstein, D. B. H., Holt, D. F., Levy, S. V. F., Paterson, M. S., and Thurston, W. P., Word processing in groups, Jones and Bartlett, 1992.Google Scholar
[20] Cenzer, D. and Remmel, J. B., Complexity-theoretic model theory and algebra, Handbook of recursive mathematics, vol. 1 (Ershov, Yu. L., Goncharov, S. S., Nerode, A., and Remmel, J. B., editors), Studies in Logic and the Foundations of Mathematics, vol. 138, North-Holland, Amsterdam, 1998, pp. 381–513.Google Scholar
[21] Colcombet, T. and C. Löding, , Transforming structures by set interpretations, Technical Report AIB-2006-07, RWTH Aachen, 2006.Google Scholar
[22] Delhommé, C., Non-automaticity of ωω , 2001, manuscript.Google Scholar
[23] Delhommé, C. The Rado graph is not automatic, 2001, manuscript.Google Scholar
[24] Delhommé, C. Automaticité des ordinaux et des graphes homogènes, Comptes Rendus Mathematique, Vol. 339 (2004), no. 1, Pp. 5–10.Google Scholar
[25] Doner, J., Tree acceptors and some of their applications, Journal of Computer and System Sciences, vol. 4 (1970), pp. 406–451.Google Scholar
[26] Eilenberg, S., Elgot, C. C., and Shepherdson, J. C., Sets recognised by n-tape automata, Journal of Algebra, vol. 13 (1969), no. 4, pp. 447–464.Google Scholar
[27] Elgot, C. C., Decision problems of finite automata design and related arithmetics, Transactions of the American Mathematical Society, vol. 98 (1961), pp. 21–51.Google Scholar
[28] Goncharov, S. S. and Knight, J. F., Computable structure and non-structure theorems, Algebra and Logic, vol. 41 (2002), no. 6, pp. 351–373.CrossRefGoogle Scholar
[29] Hella, L., Definability hierarchies of generalized quantifiers, Annals of Pure and Applied Logic, vol. 43 (1989), no. 3, pp. 235–271.CrossRefGoogle Scholar
[30] Hodgson, B. R., Théories décidables par automate fini, Ph.D. thesis, University of Montréal, 1976.Google Scholar
[31] Hodgson, B. R. On direct products of automaton decidable theories, Theoretical Computer Science, vol. 19 (1982), pp. 331–335.CrossRefGoogle Scholar
[32] Hodgson, B. R. Decidabilite par automate fini, Annales de Sciences Mathématiques du Québec, vol. 7 (1983), pp. 39–57.Google Scholar
[33] Holt, D. F., The Warwick automatic groups software, Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 25, American Mathematical Society, 1996, pp. 69–82.CrossRefGoogle Scholar
[34] Khoussainov, B. and Nerode, A., Automatic presentations of structures, Lecture Notes in Computer Science, vol. 960, 1995.Google Scholar
[35] Khoussainov, B., Nies, A., Rubin, S., and Stephan, F., Automatic structures: Richness and limitations, Logical Methods in Computer Science, vol. 3 (2007), no. 2, pp. 0–0.Google Scholar
[36] Khoussainov, B., Rubin, S., and Stephan, F., Definability and regularity in automatic structures, STACS 2004 (Diekert, V. and Habib, M., editors), Lecture Notes in Computer Science, vol. 2996, Springer, 2004, pp. 440–451.Google Scholar
[37] Khoussainov, B. Automatic linear orders and trees, ACM Transactions on Computational Logic, vol. 6 (2005), no. 4, pp. 675–700.Google Scholar
[38] Kuske, D., Is Cantor's theorem automatic?, LPAR 2003 (Vardi, M. Y. and Voronkov, A., editors), Lecture Notes in Artificial Intelligence, vol. 2850, Springer, 2003, pp. 332–345.Google Scholar
[39] Kuske, D. and Lohrey, M., First-order and counting theories of omega-automatic structures, Fakultatsbericht Nr. 2005/07, Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, September 2005.Google Scholar
[40] Libkin, L. and Neven, F., Logical definability and query languages over unranked trees, LICS 2003, IEEE Computer Society, 2003, pp. 178–187.Google Scholar
[41] Lindström, Per, First order predicate logic with generalized quantifiers, Theoria, vol. 32 (1966), pp. 186–195.Google Scholar
[42] Löding, Christof, Infinite graphs generated by tree rewriting, Ph.D. thesis, RWTH Aachen, 2003.Google Scholar
[43] Lohrey, M., Automatic structures of bounded degree, LPAR 2003 (Vardi, M. Y. and Voronkov, A., editors), Lecture Notes in Artificial Intelligence, vol. 2850, Springer, 2003, pp. 344–358.Google Scholar
[44] Michaux, C. and Point, F., Les ensembles k-reconnaissables sont définissables dans 〈N, +, Vk〉, Comptes Rendus des Séances de l'Académie des Sciences. Série I. Mathématique, vol. 303 (1986), no. 19, pp. 939–942.Google Scholar
[45] Nabebin, A. A., Multitape automata in a unary alphabet, Trudy Moskovskogo Ordena Lenina Ènergeticheskogo Instituta, vol. 292 (1976), pp. 7–11.Google Scholar
[46] Nies, A., Describing Groups, this Bulletin, vol. 13 (2007), no. 3, pp. 305–339.Google Scholar
[47] Nies, A. and Thomas, R., FA-presentable groups and rings, 2005, to appear.Google Scholar
[48] Oliver, G. and Thomas, R., Automatic presentations of finitely generated groups, STACS 2005 (Diekert, V. and Durand, B., editors), Lecture Notes in Computer Science, vol. 3404, Springer, 2005.Google Scholar
[49] Rabin, M. O., Decidability of second-order theories and automata on infinite trees, Transactions of the American Mathematical Society, vol. 141 (1969), pp. 1–35.Google Scholar
[50] Rosenstein, J. G., Linear orderings, Academic Press, 1982.Google Scholar
[51] Rubin, S., Automatic structures, Ph.D. thesis, University of Auckland, 2004.Google Scholar
[52] Stephan, F., The random graph is not automatically presentable, 2002, manuscript.Google Scholar
[53] Szilard, A., Yu, S., Zhang, K., and Shallit, J., Characterizing regular languages with polynomial densities, MFCS '92 (Havel, I. M. and Koubek, V., editors), Lecture Notes in Computer Science, vol. 629, Springer, 1992, pp. 494–503.Google Scholar
[54] Thatcher, J. W. and Wright, J. B., Generalizedfinite automata theory with an application to a decision problem of second-order logic, Mathematical Systems Theory, vol. 2 (1968), pp. 57–81.Google Scholar
[55] Thomas, W., Automata on infinite objects, Handbook of theoretical computer science (van Leeuwen, J., editor), vol. B: Formal models and semantics, Elsevier, 1990, pp. 133–191.Google Scholar
[56] Trahtenbrot, B. A., Finite automata and the logic of one-place predicates. Russian, Siberian Mathematical Journal, vol. 3 (1962), pp. 103–131, English translation: American Mathematical Society Translations, Series 2 , vol. 59 (1966), pp. 23-55.Google Scholar
[57] Villemaire, R., The theory of (〈N, +, Vk, Vl〉 is undecidable, Theoretical Computer Science, vol. 106 (1992), pp. 337–349.Google Scholar