Three lectures on automatic structures

doi:10.1017/CBO9780511778421.008

Three lectures on automatic structures

Published online by Cambridge University Press: 01 March 2011

Bakhadyr Khoussainov and

Edited by

Penelope Maddy and

Françoise Delon: Affiliation:
UFR de Mathématiques
Ulrich Kohlenbach: Affiliation:
Technische Universität, Darmstadt, Germany
Penelope Maddy: Affiliation:
University of California, Irvine
Frank Stephan: Affiliation:
National University of Singapore

Book contents

Get access

Summary

Preface. This paper grew out of three tutorial lectures on automatic structures given at the Logic Colloquium 2007 in Wrocław (Poland). The paper will follow the outline of the tutorial lectures, supplementing some material along the way. We discuss variants of automatic structures related to several models of computation: word automata, tree automata, Büchi automata, and Rabin automata. Word automata process finite strings, tree automata process finite labeled trees, Büchi automata process infinite strings, and Rabin automata process infinite binary labeled trees. Finite automata are the most commonly known in the general computer science community. An automaton of this type reads finite input strings from left to right, making state transitions along the way. Depending on its last state after processing a given string, the automaton either accepts or rejects the input string. Automatic structures are mathematical objects which can be represented by (word, tree, Büchi, or Rabin) automata. The study of properties of automatic structures is a relatively new and very active area of research.

We begin with some motivation and history for studying automatic structures. We introduce definitions of automatic structures, present examples, and discuss decidability and definability theorems. Next, we concentrate on finding natural isomorphism invariants for classes of automatic structures. These classes include well-founded partial orders, Boolean algebras, linear orders, trees, and finitely generated groups. Finally, we address the issue of complexity for automatic structures.

Type: Chapter
Information: Logic Colloquium 2007 , pp. 132 - 176

DOI: https://doi.org/10.1017/CBO9780511778421.008 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 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

[1] P. A., Abdulla, K., Čerāns, B., Jonsson, and Y., Tsay, Algorithmic analysis of programs with well quasi-ordered domains, Information and Computation, vol. 160 (2000), no. 1-2, pp. 109–127, LICS 1996, Part I (New Brunswick, NJ).Google Scholar

[2] L., Aceto, A., Burgueno, and K. G., Larsen, Model checking via reachability testing for timed automata, Proc. TACAS'98, pp. 263–280, 1998.

[3] V., Bárány, Automatic Presentations of Infinite Structures, Diploma Thesis, RWTH Aachen, Germany, 2007.

[4] V., Bárány, L., Kaiser, and S., Rubin, Cardinality and counting quantifiers on omegautomatic structures, Proc. STACS'08 (Susanne, Albers and Pascal, Weil, editors), Leibniz International Proceedings in Informatics, vol. 08001, 2008, pp. 385–396.Google Scholar

[5] C. H., Bennett, Logical reversibility of computation, International Business Machines Corporation. Journal of Research and Development, vol. 17 (1973), pp. 525–532.Google Scholar

[6] A., Blass and Y., Gurevich, Program termination and well partial orderings, ACM Transactions on Computational Logic, vol. 9 (2008), no. 3, pp. Art. 18, 26.Google Scholar

[7] A., Blumensath, Automatic Structures, Diploma Thesis, RWTH Aachen, Germany, 1999.

[8] A., Blumensath and E., Grädel, Automatic structures, 15th Annual IEEE Symposium on Logic in Computer Science (Santa Barbara, CA, 2000), IEEE Computer Society Press, Los Alamitos, CA, 2000, pp. 51–62.Google Scholar

[9] A., Bouajjani, J., Esparza, and O., Maler, Reachability analysis of pushdown automata: application to model-checking, CONCUR'97: Concurrency Theory (Warsaw), Lecture Notes in Computer Science, vol. 1243, Springer, Berlin, 1997, pp. 135–150.Google Scholar

[10] J. R., Büchi, Weak second-order arithmetic and finite automata, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 6 (1960), pp. 66–92.Google Scholar

[11] J. R., Büchi, On a decision method in restricted second order arithmetic, Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.) (E., Nagel, P., Suppes, and A., Tarski, editors), Stanford University Press, Stanford, California, 1962, pp. 1–11.Google Scholar

[12] D., Cenzer and J., Remmel, Polynomial-time versus recursive models, Annals of Pure and Applied Logic, vol. 54 (1991), no. 1, pp. 17–58.Google Scholar

[13] C., Delhommé, Automaticité des ordinaux et des graphes homogènes, Comptes Rendus Mathématique. Académie des Sciences. Paris, vol. 339 (2004), no. 1, pp. 5–10.Google Scholar

[14] J. E., Doner, Decidability of the weak second-order theory of two successors, Notices of the American Mathematical Society, vol. 12 (1965), p. 819.Google Scholar

[15] D. B. A., Epstein, James W., Cannon, Derek F., Holt, Silvio V. F., Levy, Michael S., Paterson, and William P., Thurston, Word Processing in Groups, Jones and Bartlett Publishers, Boston, MA, 1992.Google Scholar

[16] Yu. L., Ershov, Decidability of the elementary theory of distributive lattices with relative complements and the theory of filters, Algebra i Logika, vol. 3 (1964), pp. 17–38.Google Scholar

[17] Yu. L., Ershov, S. S., Goncharov, A., Nerode, J. B., Remmel, and V. W., Marek (editors), Handbook of Recursive Mathematics: Recursive Model Theory. Vol. 1, Studies in Logic and the Foundations of Mathematics, vol. 138, North-Holland, Amsterdam, 1998.Google Scholar

[18] Yu. L., Ershov, S. S., Goncharov, A., Nerode, J. B., Remmel, and V. W., Marek (editors), Handbook of Recursive Mathematics: Recursive Algebra, Analysis and Combinatorics. Vol. 2, Studies in Logic and the Foundations of Mathematics, vol. 139, North-Holland, Amsterdam, 1998.Google Scholar

[19] A. A., Fraenkel, Abstract Set Theory, Third revised edition, North-Holland, Amsterdam, 1966.Google Scholar

[20] A., Fröhlich and J. C., Shepherdson, Effective procedures in field theory, Philosophical Transactions of the Royal Society of London. Series A. Mathematical and Physical Sciences, vol. 248 (1956), pp. 407–432.Google Scholar

[21] S. S., Goncharov and J. F., Knight, Computable structure and non-structure theorems, Algebra and Logic, vol. 41 (2002), pp. 351–373.Google Scholar

[22] M., Gromov, Groups of polynomial growth and expanding maps, Institut des Hautes Études Scientifiques. Publications Mathématiques, (1981), no. 53, pp. 53–78.Google Scholar

[23] V. S., Harizanov, Pure computable model theory, Handbook of Recursive Mathematics, vol. 1 (Yu. L., Ershov, S., Goncharov, A., Nerode, and J., Remmel, editors), Studies in Logic and the Foundations of Mathematics, vol. 138, North-Holland, Amsterdam, 1998, pp. 3–114.Google Scholar

[24] J., Harrison, Recursive pseudo-well-orderings, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 526–543.Google Scholar

[25] G., Hjorth, Borel equivalence relations which are highly unfree, The Journal of Symbolic Logic, vol. 73 (2008), no. 4, pp. 1271–1277.Google Scholar

[26] G., Hjorth, B., Khoussainov, A., Montalbán, and A., Nies, From automatic structures to Borel structures, Proc. LICS'08, 2008, pp. 431–441.Google Scholar

[27] B. R., Hodgson, On direct products of automaton decidable theories, Theoretical Computer Science, vol. 19 (1982), no. 3, pp. 331–335.Google Scholar

[28] A. S., Kechris, Classical Descriptive Set Theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995.Google Scholar

[29] B., Khoussainov, J., Liu, and M., Minnes, Unary automatic graphs: an algorithmic perspective, Mathematical Structures in Computer Science. A Journal in the Applications of Categorical, Algebraic and Geometric Methods in Computer Science, vol. 19 (2009), no. 1, pp. 133–152.Google Scholar

[30] B., Khoussainov and M., Minnes, Model theoretic complexity of automatic structures (extended abstract), Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 4978, Springer, Berlin, 2008, pp. 514–525.Google Scholar

[31] B., Khoussainov and A., Nerode, Automatic presentations of structures, Logic and Computational Complexity (Indianapolis, IN, 1994), Lecture Notes in Computer Science, vol. 960, Springer, Berlin, 1995, pp. 367–392.Google Scholar

[32] B., Khoussainov, and A., Nerode, Open questions in the theory of automatic structures, Bulletin of the European Association for Theoretical Computer Science. EATCS, (2008), no. 94, pp. 181–204.Google Scholar

[33] B., Khoussainov, A., Nies, S., Rubin, and F., Stephan, Automatic structures: Richness and limitations, Logical Methods in Computer Science, (2004), pp. 2:2, 18 pp. (electronic), Special issue: Conference “Logic in Computer Science 2004”.Google Scholar

[34] B., Khoussainov, S., Rubin, and F., Stephan, On automatic partial orders, Proc. LICS'03, pp. 168–177, 2003.

[35] B., Khoussainov, S., Rubin, and F., Stephan, Definability and regularity in automatic structures, STACS 2004, Lecture Notes in Computer Science, vol. 2996, Springer, Berlin, 2004, pp. 440–451.Google Scholar

[36] S. C., Kleene, Representation of events in nerve nets and finite automata, Automata Studies, Annals of Mathematics Studies, vol. 34, Princeton University Press, Princeton, N.J., 1956, pp. 3–41.Google Scholar

[37] J. F., Knight and J., Millar, Computable structures of rank ωCK1, Submitted to J. Math. Logic; posted on arXiv 25 Aug. 2005.Google Scholar

[38] D., Kuske and M., Lohrey, First-order and counting theories of ω-automatic structures, Foundations of Software Science and Computation Structures, Lecture Notes in Computer Science, vol. 3921, Springer, Berlin, 2006, pp. 322–336.Google Scholar

[39] J., Liu, Automatic structures (provisional title), Ph.D. thesis, University of Auckland, Auckland, in progress.

[40] A. I., Mal'cev, Constructive algebras. I, Akademiya Nauk SSSR i Moskovskoe Matematicheskoe Obshchestvo. Uspekhi Matematicheskikh Nauk, vol. 16 (1961), no. 3 (99), pp. 3–60.Google Scholar

[41] M., Minnes, Automatic structures (provisional title), Ph.D. thesis, Cornell University, Ithaca, NY, 2008.

[42] M., Nadel, ℒω1ω and admissible fragments, Model-Theoretic Logics (K. J., Barwise and S., Feferman, editors), Perspectives in Mathematical Logic, Springer, New York, 1985, pp. 271–316.Google Scholar

[43] A., Nerode and J. B., Remmel, Polynomial time equivalence types, Logic and Computation (Pittsburgh, PA, 1987), Contemporary Mathematics, vol. 106, Amer. Math. Soc., Providence, RI, 1990, pp. 221–249.Google Scholar

[44] A., Nies, Describing groups, The Bulletin of Symbolic Logic, vol. 13 (2007), no. 3, pp. 305–339.Google Scholar

[45] G. A., Noskov, The elementary theory of a finitely generated almost solvable group, Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, vol. 47 (1983), no. 3, pp. 498–517, (Russian); Math. USSR Izv. 22, 465–482, 1984 (English translation).Google Scholar

[46] G. P., Oliver and R. M., Thomas, Automatic presentations for finitely generated groups, STACS 2005, Lecture Notes in Computer Science, vol. 3404, Springer, Berlin, 2005, pp. 693–704.Google Scholar

[47] M. O., Rabin, Computable algebra, general theory and theory of computable fields., Transactions of the American Mathematical Society, vol. 95 (1960), pp. 341–360.Google Scholar

[48] M. O., Rabin, Decidability of second-order theories and automata on infinite trees., Transactions of the American Mathematical Society, vol. 141 (1969), pp. 1–35.Google Scholar

[49] N. S., Romanovskiĭ, The elementary theory of an almost polycyclic group, Matematicheskiĭ Sbornik. Novaya Seriya, vol. 111(153) (1980), no. 1, pp. 135–143, 160, (Russian); Math. USSR Sb., 39, 1981 (English translation).Google Scholar

[50] J., Rotman, An Introduction to the Theory of Groups, fourth ed., Graduate Texts in Mathematics, vol. 148, Springer-Verlag, New York, 1995.Google Scholar

[51] S., Rubin, Automatic structures, Ph.D. thesis, University of Auckland, Auckland, 2004.

[52] S., Rubin, Automata presenting structures: A survey of the finite string case, The Bulletin of Symbolic Logic, vol. 14 (2008), no. 2, pp. 169–209.Google Scholar

[53] T., Scanlon, Infinite finitely generated fields are biinterpretable with ℕ, Journal of the American Mathematical Society, vol. 21 (2008), no. 3, pp. 893–908.Google Scholar

[54] D., Scott, Logic with denumerably long formulas and finite strings of quantifiers, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley) (J., Addison, L., Henkin, and A., Tarski, editors), North-Holland, Amsterdam, 1965, pp. 329–341.Google Scholar

[55] G. S., Shmelev, Classification of indecomposable finite-dimensional representations of the Lie superalgebra W(0, 2), Doklady Bolgarskoĭ Akademii Nauk. Comptes Rendus de l'Académie Bulgare des Sciences, vol. 35 (1982), no. 8, pp. 1025–1027 (Russian).Google Scholar

[56] A., Tarski, A Decision Method for Elementary Algebra and Geometry, RAND Corporation, Santa Monica, Calif., 1948.Google Scholar

[57] A, Tarski, Arithmetical classes and types of boolean algebras, American Mathematical Society. Bulletin, vol. 55 (1949), p. 63.Google Scholar

[58] J. W., Thatcher and J. B., Wright, Generalized finite automata theory with an application to a decision problem of second-order logic, Mathematical Systems Theory. An International Journal on Mathematical Computing Theory, vol. 2 (1968), pp. 57–81.Google Scholar

[59] W., Thomas, Automata on infinite objects, Handbook of Theoretical computer Science, vol. B, Elsevier, Amsterdam, 1990, pp. 133–191.Google Scholar

Book contents

Three lectures on automatic structures

Summary

Access options

References

Save book to Kindle

Save book to Dropbox

Save book to Google Drive