Advice Automatic Structures and Uniformly Automatic Classes

Authors Faried Abu Zaid, Erich Grädel, Frederic Reinhardt



PDF
Thumbnail PDF

File

LIPIcs.CSL.2017.35.pdf
  • Filesize: 0.55 MB
  • 20 pages

Document Identifiers

Author Details

Faried Abu Zaid
Erich Grädel
Frederic Reinhardt

Cite AsGet BibTex

Faried Abu Zaid, Erich Grädel, and Frederic Reinhardt. Advice Automatic Structures and Uniformly Automatic Classes. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CSL.2017.35

Abstract

We study structures that are automatic with advice. These are structures that admit a presentation by finite automata (over finite or infinite words or trees) with access to an additional input,called an advice. Over finite words, a standard example of a structure that is automatic with advice, but not automatic in the classical sense, is the additive group of rational numbers (Q,+). By using a set of advices rather than a single advice, this leads to the new concept of a parameterised automatic presentation as a means to uniformly represent a whole class of structures. The decidability of the first-order theory of such a uniformly automatic class reduces to the decidability of the monadic second-order theory of the set of advices that are used in the presentation. Such decidability results also hold for extensions of first-order logic by regularity preserving quantifiers, such as cardinality quantifiers and Ramsey quantifiers. To investigate the power of this concept, we present examples of structures and classes of structures that are automatic with advice but not without advice, and we prove classification theorems for the structures with an advice automatic presentation for several algebraic domains. In particular, we prove that the class of all torsion-free Abelian groups of rank one is uniformly omega-automatic and that there is a uniform omega-tree-automatic presentation of the class of all Abelian groups up to elementary equivalence and of the class of all countable divisible Abelian groups. On the other hand we show that every uniformly omega-automatic class of Abelian groups must have bounded rank. While for certain domains, such as trees and Abelian groups, it turns out that automatic presentations with advice are capable of presenting significantly more complex structures than ordinary automatic presentations, there are other domains, such as Boolean algebras, where this is provably not the case. Further, advice seems to not be of much help for representing some particularly relevant examples of structures with decidable theories, most notably the field of reals. Finally we study closure properties for several kinds of uniformly automatic classes, and decision problems concerning the number of non-isomorphic models in uniformly automatic classes with the unique representation property.
Keywords
  • automatic structures
  • algorithmic model theory
  • decidable theories
  • torsion-free abelian groups
  • first-order logic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Faried Abu Zaid, Erich Grädel, and Łukasz Kaiser. The Field of Reals is not omega-Automatic. In Christoph Dürr and Thomas Wilke, editors, Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, 2012. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2012.577.
  2. Reinhold Baer. Abelian groups without elements of finite order. Duke Mathematical Journal, 3:68-122, 1937. URL: http://dx.doi.org/10.1215/S0012-7094-37-00308-9.
  3. V. Bárány, E. Grädel, and S. Rubin. Automata-based presentations of infinite structures. In Finite and Algorithmic Model Theory, London Mathematical Society Lecture Note Series (No. 379). Cambridge University Press, 2011. URL: http://dx.doi.org/10.1017/CBO9780511974960.002.
  4. Achim Blumensath. Automatic Structures. Diploma thesis, RWTH-Aachen, 1999. URL: http://www.logic.rwth-aachen.de/pub/blume/AutStr.ps.gz.
  5. Achim Blumensath and Erich Grädel. Finite Presentations of Infinite Structures: Automata and Interpretations. Theory of Computing Systems, 37:641-674, 2004. URL: http://dx.doi.org/10.1007/s00224-004-1133-y.
  6. Christian Choffrut and Serge Grigorieff. Uniformization of rational relations. In Jewels Are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pages 59-71. Springer-Verlag, 1999. URL: http://dx.doi.org/10.1007/978-3-642-60207-8_6.
  7. Thomas Colcombet and Christof Löding. Transforming structures by set interpretations. Logical Methods in Computer Science, 3(2), 2007. URL: http://dx.doi.org/10.2168/LMCS-3(2:4)2007.
  8. László Fuchs. Infinite Abelian Groups, volume Bd. 1. Academic Press, 1970. URL: http://dx.doi.org/10.1007/978-3-319-19422-6.
  9. Sergey Goncharov. Countable Boolean Algebras and Decidability. Siberian School of Algebra and Logic. Springer, 1997. Google Scholar
  10. P. A. Grillet. Commutative Semigroups. Advances in Mathematics. Springer US, 2004. URL: http://dx.doi.org/10.1007/978-1-4757-3389-1.
  11. Wilfrid Hodges. Model Theory. Number 42 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1993. URL: http://dx.doi.org/10.1017/CBO9780511551574.
  12. Łukasz Kaiser, Sasha Rubin, and Vince Bárány. Cardinality and counting quantifiers on omega-automatic structures. In Susanne Albers and Pascal Weil, editors, Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008, pages 385-396, 2008. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1360.
  13. Alexander Kartzow and Philipp Schlicht. Structures without scattered-automatic presentation. In Paola Bonizzoni, Vasco Brattka, and Benedikt Löwe, editors, The Nature of Computation. Logic, Algorithms, Applications, volume 7921 of Lecture Notes in Computer Science, pages 273-283. Springer Berlin Heidelberg, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39053-1_32.
  14. Bakhadyr Khoussainov and Anil Nerode. Automatic presentations of structures. In Selected Papers from the International Workshop on Logical and Computational Complexity, LCC'94, pages 367-392. Springer-Verlag, 1995. Google Scholar
  15. Bakhadyr Khoussainov, Sasha Rubin, A. Nies, and F. Stephan. Automatic structures: Richness and limitations. In LICS 2004, pages 44-53, 2004. URL: http://dx.doi.org/10.1109/LICS.2004.1319599.
  16. Alex Kruckman, Sasha Rubin, John Sheridan, and Ben Zax. A Myhill-Nerode theorem for automata with advice. Electronic Proceedings in Theoretical Computer Science, 96:238-246, October 2012. URL: http://dx.doi.org/10.4204/EPTCS.96.18.
  17. Dietrich Kuske. Is Ramsey’s theorem omega-automatic? In Jean-Yves Marion and Thomas Schwentick, editors, 27th International Symposium on Theoretical Aspects of Computer Science, volume 5 of Leibniz International Proceedings in Informatics (LIPIcs), pages 537-548. Schloss DagstuhlendashLeibniz-Zentrum fuer Informatik, 2010. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2483.
  18. Dietrich Kuske, Jiamou Liu, and Markus Lohrey. The isomorphism problem on classes of automatic structures. In LICS 2010, pages 160-169, 2010. URL: http://dx.doi.org/10.1090/S0002-9947-2013-05766-2.
  19. André Nies. Describing groups. Bulletin of Symbolic Logic, 13(3):305-339, September 2007. URL: http://dx.doi.org/10.2178/bsl/1186666149.
  20. Sasha Rubin. Automata presenting structures: A survey of the finite string case. Bulletin of Symbolic Logic, 14(2):169-209, 2008. URL: http://dx.doi.org/10.2178/bsl/1208442827.
  21. Wanda Szmielew. Elementary properties of abelian groups. Fundamenta Mathematicae, 41(2):203-271, 1955. Google Scholar
  22. Simon Thomas. The classification problem for torsion-free abelian groups of finite rank. J. Amer. Math. Soc, 16:233-258, 2001. Google Scholar
  23. Todor Tsankov. The additive group of the rationals does not have an automatic presentation. J. Symb. Log., 76(4):1341-1351, 2011. URL: http://dx.doi.org/10.2178/jsl/1318338853.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail