Book contents
- Frontmatter
- Contents
- Introduction
- Speakers and Titles
- Decorated linear order types and the theory of concatenation
- Cardinal preserving elementary embeddings
- Proof interpretations and majorizability
- Proof mining in practice
- Cardinal structure under AD
- Three lectures on automatic structures
- Pillay's conjecture and its solution—a survey
- Proof theory and meaning: On the context of deducibility
- Bounded super real closed rings
- Analytic combinatorics of the transfinite: A unifying Tauberian perspective
- References
Three lectures on automatic structures
Published online by Cambridge University Press: 01 March 2011
Book contents
- Frontmatter
- Contents
- Introduction
- Speakers and Titles
- Decorated linear order types and the theory of concatenation
- Cardinal preserving elementary embeddings
- Proof interpretations and majorizability
- Proof mining in practice
- Cardinal structure under AD
- Three lectures on automatic structures
- Pillay's conjecture and its solution—a survey
- Proof theory and meaning: On the context of deducibility
- Bounded super real closed rings
- Analytic combinatorics of the transfinite: A unifying Tauberian perspective
- References
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 - 176Publisher: Cambridge University PressPrint publication year: 2010
References
[1] , , , and , 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] , , and , Model checking via reachability testing for timed automata, Proc. TACAS'98, pp. 263–280, 1998.
[3] , Automatic Presentations of Infinite Structures, Diploma Thesis, RWTH Aachen, Germany, 2007.
[4] , , and , Cardinality and counting quantifiers on omegautomatic structures, Proc. STACS'08 ( and , editors), Leibniz International Proceedings in Informatics, vol. 08001, 2008, pp. 385–396.Google Scholar
[5] , Logical reversibility of computation, International Business Machines Corporation. Journal of Research and Development, vol. 17 (1973), pp. 525–532.Google Scholar
[6] and , Program termination and well partial orderings, ACM Transactions on Computational Logic, vol. 9 (2008), no. 3, pp. Art. 18, 26.Google Scholar
[7] , Automatic Structures, Diploma Thesis, RWTH Aachen, Germany, 1999.
[8] and , 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] , , and , 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] , 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] , On a decision method in restricted second order arithmetic, Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.) (, , and , editors), Stanford University Press, Stanford, California, 1962, pp. 1–11.Google Scholar
[12] and , Polynomial-time versus recursive models, Annals of Pure and Applied Logic, vol. 54 (1991), no. 1, pp. 17–58.Google Scholar
[13] , 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] , Decidability of the weak second-order theory of two successors, Notices of the American Mathematical Society, vol. 12 (1965), p. 819.Google Scholar
[15] , , , , , and , Word Processing in Groups, Jones and Bartlett Publishers, Boston, MA, 1992.Google Scholar
[16] , 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] , , , , and (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] , , , , and (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
[20] and , 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] and , Computable structure and non-structure theorems, Algebra and Logic, vol. 41 (2002), pp. 351–373.Google Scholar
[22] , Groups of polynomial growth and expanding maps, Institut des Hautes Études Scientifiques. Publications Mathématiques, (1981), no. 53, pp. 53–78.Google Scholar
[23] , Pure computable model theory, Handbook of Recursive Mathematics, vol. 1 (, , , and , editors), Studies in Logic and the Foundations of Mathematics, vol. 138, North-Holland, Amsterdam, 1998, pp. 3–114.Google Scholar
[24] , Recursive pseudo-well-orderings, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 526–543.Google Scholar
[25] , Borel equivalence relations which are highly unfree, The Journal of Symbolic Logic, vol. 73 (2008), no. 4, pp. 1271–1277.Google Scholar
[26] , , , and , From automatic structures to Borel structures, Proc. LICS'08, 2008, pp. 431–441.Google Scholar
[27] , On direct products of automaton decidable theories, Theoretical Computer Science, vol. 19 (1982), no. 3, pp. 331–335.Google Scholar
[28] , Classical Descriptive Set Theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995.Google Scholar
[29] , , and , 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] and , 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] and , 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] , and , 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] , , , and , 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] , , and , On automatic partial orders, Proc. LICS'03, pp. 168–177, 2003.
[35] , , and , Definability and regularity in automatic structures, STACS 2004, Lecture Notes in Computer Science, vol. 2996, Springer, Berlin, 2004, pp. 440–451.Google Scholar
[36] , 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] and , Computable structures of rank ωCK1, Submitted to J. Math. Logic; posted on arXiv 25 Aug. 2005.Google Scholar
[38] and , 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] , Automatic structures (provisional title), Ph.D. thesis, University of Auckland, Auckland, in progress.
[40] , 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] , Automatic structures (provisional title), Ph.D. thesis, Cornell University, Ithaca, NY, 2008.
[42] , ℒω1ω and admissible fragments, Model-Theoretic Logics ( and , editors), Perspectives in Mathematical Logic, Springer, New York, 1985, pp. 271–316.Google Scholar
[43] and , 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] , Describing groups, The Bulletin of Symbolic Logic, vol. 13 (2007), no. 3, pp. 305–339.Google Scholar
[45] , 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] and , Automatic presentations for finitely generated groups, STACS 2005, Lecture Notes in Computer Science, vol. 3404, Springer, Berlin, 2005, pp. 693–704.Google Scholar
[47] , Computable algebra, general theory and theory of computable fields., Transactions of the American Mathematical Society, vol. 95 (1960), pp. 341–360.Google Scholar
[48] , 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] , 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] , An Introduction to the Theory of Groups, fourth ed., Graduate Texts in Mathematics, vol. 148, Springer-Verlag, New York, 1995.Google Scholar
[51] , Automatic structures, Ph.D. thesis, University of Auckland, Auckland, 2004.
[52] , 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] , Infinite finitely generated fields are biinterpretable with ℕ, Journal of the American Mathematical Society, vol. 21 (2008), no. 3, pp. 893–908.Google Scholar
[54] , Logic with denumerably long formulas and finite strings of quantifiers, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley) (, , and , editors), North-Holland, Amsterdam, 1965, pp. 329–341.Google Scholar
[55] , 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 Decision Method for Elementary Algebra and Geometry, RAND Corporation, Santa Monica, Calif., 1948.Google Scholar
[57] , Arithmetical classes and types of boolean algebras, American Mathematical Society. Bulletin, vol. 55 (1949), p. 63.Google Scholar
[58] and , 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] , Automata on infinite objects, Handbook of Theoretical computer Science, vol. B, Elsevier, Amsterdam, 1990, pp. 133–191.Google Scholar
- 17
- Cited by