Automata presenting structures: A survey of the finite string case

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

Abstract

A structure has a (finite-string) automatic presentation if 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,174

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

Computational Semantics for Monadic Quantifiers.Marcin Mostowski - 1998 - Journal of Applied Non--Classical Logics 8 (1-2):107--121.
Finitely Constrained Classes of Homogeneous Directed Graphs.Brenda J. Latka - 1994 - Journal of Symbolic Logic 59 (1):124-139.
Weak Cardinality Theorems.Till Tantau - 2005 - Journal of Symbolic Logic 70 (3):861 - 878.
On Finite Rigid Structures.Yuri Gurevich & Saharon Shelah - 1996 - Journal of Symbolic Logic 61 (2):549-562.
Countable Structures of Given Age.H. D. Macpherson, M. Pouzet & R. E. Woodrow - 1992 - Journal of Symbolic Logic 57 (3):992-1010.
Modifiable Automata Self-Modifying Automata.J.-P. Moulin - 1992 - Acta Biotheoretica 40 (2-3):195-204.
Hereditary Undecidability of Some Theories of Finite Structures.Ross Willard - 1994 - Journal of Symbolic Logic 59 (4):1254-1262.

Analytics

Added to PP
2010-08-30

Downloads
37 (#312,308)

6 months
1 (#413,740)

Historical graph of downloads
How can I increase my downloads?

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