Survey of automatic structures

Bulletin of Symbolic Logic 14 (2):169-200 (2008)
  Copy   BIBTEX

Abstract

A structure has a automatic presentationif 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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,181

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Automata Presenting Structures: A Survey of the Finite String Case.Sasha Rubin - 2008 - Bulletin of Symbolic Logic 14 (2):169-209.
Automatic Structures of Bounded Degree Revisited.Dietrich Kuske & Markus Lohrey - 2011 - Journal of Symbolic Logic 76 (4):1352-1380.
A Hierarchy of Tree-Automatic Structures.Olivier Finkel & Stevo Todorčević - 2012 - Journal of Symbolic Logic 77 (1):350-368.
Automatic Continuity of Group Homomorphisms.Christian Rosendal - 2009 - Bulletin of Symbolic Logic 15 (2):184-214.
Automatic Checking Properties of Non-Classical Logics.Pavel Schreiner - 2006 - Journal of Applied Non-Classical Logics 16 (3-4):507-516.
Model-Theoretic Complexity of Automatic Structures.Bakhadyr Khoussainov & Mia Minnes - 2010 - Annals of Pure and Applied Logic 161 (3):416-426.
Ethical Automaticity.Michael Brownstein & Alex Madva - 2012 - Philosophy of the Social Sciences 42 (1):68-98.
How Automatic and Representational is Empathy, and Why.Martin L. Hoffman - 2001 - Behavioral and Brain Sciences 25 (1):38-39.

Analytics

Added to PP
2014-03-12

Downloads
4 (#1,230,414)

6 months
1 (#413,813)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Automatic Models of First Order Theories.Pavel Semukhin & Frank Stephan - 2013 - Annals of Pure and Applied Logic 164 (9):837-854.
The Isomorphism Problem for Ω-Automatic Trees.Dietrich Kuske, Jiamou Liu & Markus Lohrey - 2013 - Annals of Pure and Applied Logic 164 (1):30-48.
An Example of an Automatic Graph of Intermediate Growth.Alexei Miasnikov & Dmytro Savchuk - 2015 - Annals of Pure and Applied Logic 166 (10):1037-1048.

Add more citations

References found in this work

Weak Second‐Order Arithmetic and Finite Automata.J. Richard Büchi - 1960 - Mathematical Logic Quarterly 6 (1-6):66-92.
Definability Hierarchies of General Quantifiers.Lauri Hella - 1989 - Annals of Pure and Applied Logic 43 (3):235.
Linear Orderings.Joseph G. Rosenstein - 1983 - Journal of Symbolic Logic 48 (4):1207-1209.

Add more references