Automatic models of first order theories

DOI10.1016/J.APAL.2013.03.001MaRDI QIDQ387121zbMATH OpenOpenAlexFDO

Publication date 11 December 2013

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2013.03.001

automatic structures model theory prime model saturated model uncountably categorical theory

Categoricity and completeness of theories (03C35) Models with special properties (saturated, rigid, etc.) (03C50) Computable structure theory, computable model theory (03C57) Automata and formal grammars in connection with logical questions (03D05) Theory of numerations, effectively presented structures (03D45)

Review text

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.NEWLINENEWLINE\end{itemize}}

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Automatic models of first order theories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q387121)