Annals of Pure and Applied Logic 164 (9):837-854 (2013)

Abstract
Khoussainov and Nerode [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: There is an uncountably categorical but not countably categorical theory for which only the prime model is automatic; There are complete theories with exactly 3,4,5,…3,4,5,… countable models, respectively, and every countable model is automatic; There is a complete theory for which exactly 2 models have an automatic presentation; If LOGSPACE=PLOGSPACE=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; 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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2013.03.001
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,410
Through your library

References found in this work BETA

[Introduction].Wilfrid Hodges - 1986 - Journal of Symbolic Logic 51 (4):865.
On Strongly Minimal Sets.J. T. Baldwin & A. H. Lachlan - 1971 - Journal of Symbolic Logic 36 (1):79-96.
[Omnibus Review].H. Jerome Keisler - 1970 - Journal of Symbolic Logic 35 (2):342-344.
Computable Models of Theories with Few Models.Bakhadyr Khoussainov, Andre Nies & Richard A. Shore - 1997 - Notre Dame Journal of Formal Logic 38 (2):165-178.
Describing Groups.André Nies - 2007 - Bulletin of Symbolic Logic 13 (3):305-339.

View all 11 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Analytics

Added to PP index
2013-12-12

Total views
67 ( #172,999 of 2,519,700 )

Recent downloads (6 months)
1 ( #406,314 of 2,519,700 )

How can I increase my downloads?

Downloads

My notes