Automatic Structures: Richness and Limitations

Bakhadyr Khoussainov; Andre Nies; Sasha Rubin; Frank Stephan

doi:10.2168/LMCS-3(2:2)2007

Bakhadyr Khoussainov ; Andre Nies ; Sasha Rubin ; Frank Stephan - Automatic Structures: Richness and Limitations

lmcs:2219 - Logical Methods in Computer Science, April 26, 2007, Volume 3, Issue 2 - https://doi.org/10.2168/LMCS-3(2:2)2007

Automatic Structures: Richness and LimitationsArticle

Authors: Bakhadyr Khoussainov ; Andre Nies ; Sasha Rubin ; Frank Stephan

We study the existence of automatic presentations for various algebraic structures. An automatic presentation of a structure is a description of the universe of the structure by a regular set of words, and the interpretation of the relations by synchronised automata. Our first topic concerns characterising classes of automatic structures. We supply a characterisation of the automatic Boolean algebras, and it is proven that the free Abelian group of infinite rank, as well as certain Fraisse limits, do not have automatic presentations. In particular, the countably infinite random graph and the random partial order do not have automatic presentations. Furthermore, no infinite integral domain is automatic. Our second topic is the isomorphism problem. We prove that the complexity of the isomorphism problem for the class of all automatic structures is \Sigma_1^1-complete.

https://doi.org/10.2168/LMCS-3(2:2)2007

Source: arXiv.org:cs/0703064

Volume: Volume 3, Issue 2

Published on: April 26, 2007

Submitted on: September 15, 2006

Keywords: Computer Science - Discrete Mathematics,Computer Science - Logic in Computer Science,F.1.1,F.4.3

Licence: arXiv.org - Assumed non-exclusive license to distribute

Bibliographic References

29 Documents citing this article

Richard Krogman;Douglas Cenzer, 2022, Complexity of injection structures induced by finite state transducers, Journal of Logic and Computation, 32, 8, pp. 1504-1530, 10.1093/logcom/exac065.

Ziyuan Gao;Sanjay Jain;Ji Qi;Philipp Schlicht;Frank Stephan;et al., Lecture notes in computer science, Ordered Semiautomatic Rings with Applications to Geometry, pp. 141-153, 2020, 10.1007/978-3-030-40608-0_9, https://doi.org/10.1007/978-3-030-40608-0_9.

Alexander G. Melnikov;Keng Meng Ng, 2019, The back-and-forth method and computability without delay, Israel Journal of Mathematics, 234, 2, pp. 959-1000, 10.1007/s11856-019-1948-5.

Martin Huschenbett;Alexander Kartzow;Philipp Schlicht, 2017, Pumping for ordinal-automatic structures1, Computability, 6, 2, pp. 125-164, 10.3233/com-160057.

Sanjay Jain;Bakhadyr Khoussainov;Philipp Schlicht;Frank Stephan, 2016, Tree-automatic scattered linear orders, Theoretical Computer Science, 626, pp. 83-96, 10.1016/j.tcs.2016.02.008.

A. S. Denisenko;N. T. Kogabaev, 2014, On automatic presentations of projective planes, Siberian Mathematical Journal, 55, 1, pp. 53-62, 10.1134/s0037446614010078.

Dietrich Kuske, 2014, Isomorphisms of scattered automatic linear orders, Theoretical Computer Science, 533, pp. 46-63, 10.1016/j.tcs.2014.03.022, https://doi.org/10.1016/j.tcs.2014.03.022.

Alexander G. Melnikov;André Nies, Massey Research Online (Massey University), The Classification Problem for Compact Computable Metric Spaces, pp. 320-328, 2013, 10.1007/978-3-642-39053-1_37, http://www.newton.ac.uk/files/preprints/ni13004_0.pdf.

Alexander Kartzow;Philipp Schlicht, arXiv (Cornell University), Structures without Scattered-Automatic Presentation, pp. 273-283, 2013, 10.1007/978-3-642-39053-1_32, http://arxiv.org/abs/1304.0912.

Faried Abu Zaid;Erich Grädel;Łukasz Kaiser;Wied Pakusa, 2013, Model-Theoretic Properties of ω-Automatic Structures, Theory of Computing Systems, 55, 4, pp. 856-880, 10.1007/s00224-013-9508-6.

Markus Lohrey;Christian Mathissen, 2013, Isomorphism of regular trees and words, Information and Computation, 224, pp. 71-105, 10.1016/j.ic.2013.01.002, https://doi.org/10.1016/j.ic.2013.01.002.

Swarat Chaudhuri;Sriram Sankaranarayanan;Moshe Y. Vardi, Rice Digital Scholarship Archive (Rice University), Regular Real Analysis, 2013, New Orleans, LA, USA, 10.1109/lics.2013.57, http://hdl.handle.net/1911/78493.

Alexander Kartzow;Jiamou Liu;Markus Lohrey, Common Library Network (Der Gemeinsame Bibliotheksverbund), Tree-Automatic Well-Founded Trees, pp. 363-373, 2012, 10.1007/978-3-642-30870-3_37, https://www.db-thueringen.de/receive/dbt_mods_00022625.

Dietrich Kuske;Jiamou Liu;Markus Lohrey, 2012, The isomorphism problem for ω-automatic trees, Annals of Pure and Applied Logic, 164, 1, pp. 30-48, 10.1016/j.apal.2012.09.001, https://doi.org/10.1016/j.apal.2012.09.001.

Olivier Finkel;Stevo Todorčević, 2012, A hierarchy of tree-automatic structures, 77, 1, pp. 350-368, 10.2178/jsl/1327068708, https://hal.science/hal-00638581.

Dietrich Kuske, Lecture notes in computer science, Where Automatic Structures Benefit from Weighted Automata, pp. 257-271, 2011, 10.1007/978-3-642-24897-9_12.

Dietrich Kuske;Thomas Weidner, Lecture notes in computer science, Size and Computation of Injective Tree Automatic Presentations, pp. 424-435, 2011, 10.1007/978-3-642-22993-0_39.

Markus Lohrey;Christian Mathissen, arXiv (Cornell University), Isomorphism of Regular Trees and Words, pp. 210-221, 2011, 10.1007/978-3-642-22012-8_16, https://arxiv.org/abs/1102.2782.

Todor Tsankov, 2011, The additive group of the rationals does not have an automatic presentation, arXiv (Cornell University), 76, 4, pp. 1341-1351, 10.2178/jsl/1318338853.

Victor Marek;Jeffrey B. Remmel, CiteSeer X (The Pennsylvania State University), Effectively Reasoning about Infinite Sets in Answer Set Programming, pp. 131-147, 2011, 10.1007/978-3-642-20832-4_9, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.299.5585.

Dietrich Kuske;Jiamou Liu;Markus Lohrey, arXiv (Cornell University), The Isomorphism Problem for ω-Automatic Trees, pp. 396-410, 2010, 10.1007/978-3-642-15205-4_31.

Dietrich Kuske;Jiamou Liu;Markus Lohrey, Open Research (Auckland University of Technology), The Isomorphism Problem on Classes of Automatic Structures, 94, pp. 160-169, 2010, Edinburgh, United Kingdom, 10.1109/lics.2010.10, https://hdl.handle.net/10292/2808.

Dietrich Kuske;Markus Lohrey, 2010, Some natural decision problems in automatic graphs, Journal of Symbolic Logic, 75, 2, pp. 678-710, 10.2178/jsl/1268917499.

Felix Klaedtke, 2010, Ehrenfeucht–Fraïssé goes automatic for real addition, Information and Computation, 208, 11, pp. 1283-1295, 10.1016/j.ic.2010.07.003, https://doi.org/10.1016/j.ic.2010.07.003.

Olivier Finkel;Stevo Todorčević, 2010, The isomorphism relation between tree-automatic Structures, 8, 2, pp. 299-313, 10.2478/s11533-010-0014-7, https://hal.archives-ouvertes.fr/hal-00497724.

Dietrich Kuske, Lecture notes in computer science, Theories of Automatic Structures and Their Complexity, pp. 81-98, 2009, 10.1007/978-3-642-03564-7_5.

Victor W. Marek;Jeffrey B. Remmel, 2009, The complexity of recursive constraint satisfaction problems, Annals of Pure and Applied Logic, 161, 3, pp. 447-457, 10.1016/j.apal.2009.07.005.

Sasha Rubin, 2008, Automata Presenting Structures: A Survey of the Finite String Case, Bulletin of Symbolic Logic, 14, 2, pp. 169-209, 10.2178/bsl/1208442827.

Victor Marek;Jeffrey B. Remmel, Lecture notes in computer science, Automata and Answer Set Programming, pp. 323-337, 2008, 10.1007/978-3-540-92687-0_22.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1590 times.

This article's PDF has been downloaded 508 times.