Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-17T20:57:55.621Z Has data issue: false hasContentIssue false

Automata Presenting Structures: A Survey of the Finite String Case

Published online by Cambridge University Press:  15 January 2014

Sasha Rubin*
Affiliation:
Department of Computer Science, University of Auckland, New Zealand E-mail: rubin@cs.auckland.ac.nz

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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable