Automatic models of first order theories (Q387121): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / 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. \end{itemize}} | |||
Property / 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. \end{itemize}} / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03C57 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03D45 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03C35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03D05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03C50 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6237517 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
automatic structures | |||
Property / zbMATH Keywords: automatic structures / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
model theory | |||
Property / zbMATH Keywords: model theory / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
uncountably categorical theory | |||
Property / zbMATH Keywords: uncountably categorical theory / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
saturated model | |||
Property / zbMATH Keywords: saturated model / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
prime model | |||
Property / zbMATH Keywords: prime model / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Andrey S. Morozov / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.apal.2013.03.001 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1991893284 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On strongly minimal sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: BREAKING UP FINITE AUTOMATA PRESENTABLE TORSION-FREE ABELIAN GROUPS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Automaticity of ordinals and of homogeneous graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An application of games to the completeness problem for formalized theories / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5799960 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3230355 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4165359 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An uncountably categorical theory whose only computably presentable model is saturated / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4003410 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3312199 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4501152 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3396632 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Automatic Structures: Richness and Limitations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computable models of theories with few models / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4449538 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Isomorphism Problem for ω-Automatic Trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Deciding the isomorphism problem in classes of unary automatic structures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Describing Groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finite automata presentable Abelian groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Automata Presenting Structures: A Survey of the Finite String Case / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The additive group of the rationals does not have an automatic presentation / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 04:25, 7 July 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