Automatic models of first order theories (Q387121): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:07, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Automatic models of first order theories |
scientific article |
Statements
Automatic models of first order theories (English)
0 references
11 December 2013
0 references
The authors prove the following results which answer some questions formulated in [\textit{B. Khoussainov} and \textit{A. Nerode}, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 94, 181--204 (2008; Zbl 1169.03352)]: {\parindent=6mm (from the author's summary) \begin{itemize} \item[(1)] There is an uncountably categorical but not countably categorical theory for which only the prime model is automatic. \item [(2)] There are complete theories with exactly 3, 4, 5, . . . countable models, respectively, and every countable model is automatic. \item [(3)] There is a complete theory for which exactly 2 models have an automatic presentation. \item [(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. \item [(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. \end{itemize}}
0 references
automatic structures
0 references
model theory
0 references
uncountably categorical theory
0 references
saturated model
0 references
prime model
0 references