Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.apal.2013.03.001
Title: Automatic models of first order theories
Authors: Semukhin, P.
Stephan, F. 
Keywords: Automatic structures
Model theory
Issue Date: Sep-2013
Citation: Semukhin, P., Stephan, F. (2013-09). Automatic models of first order theories. Annals of Pure and Applied Logic 164 (9) : 837-854. ScholarBank@NUS Repository. https://doi.org/10.1016/j.apal.2013.03.001
Abstract: Khoussainov and Nerode (2008) [14] posed various open questions on model-theoretic properties of automatic structures. In this work we answer some of these questions by showing the following results: (1) There is an uncountably categorical but not countably categorical theory for which only the prime model is automatic; (2) There are complete theories with exactly 3, 4, 5,... countable models, respectively, and every countable model is automatic; (3) There is a complete theory for which exactly 2 models have an automatic presentation; (4) If LOGSPACE=P then there is an uncountably categorical but not countably categorical theory for which the prime model does not have an automatic presentation but all the other countable models are automatic; (5) There is a complete theory with countably many countable models for which the saturated model has an automatic presentation but the prime model does not have one. © 2013 Elsevier B.V.
Source Title: Annals of Pure and Applied Logic
URI: http://scholarbank.nus.edu.sg/handle/10635/102909
ISSN: 01680072
DOI: 10.1016/j.apal.2013.03.001
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.