Geodesic
Automatic structures and the theory of lists
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 12 (2015), pp. 714-722

Voir la notice de l'article provenant de la source Math-Net.Ru

Goncharov constructed the axiomatic theory of linear lists over the elements of a given data type. We study algorithmic complexity for models of this theory. We prove that the enriched list structure over a finite set of atoms is automatically presentable, and the enriched list structure over an infinite set of atoms has no automatic presentations.
Keywords: automatic structure, linear list, theory of lists, decidable model, list superstructure. 
@article{SEMR_2015_12_a22,
     author = {N. A. Bazhenov},
     title = {Automatic structures and the theory of lists},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {714--722},
     publisher = {mathdoc},
     volume = {12},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2015_12_a22/}
}
TY  - JOUR
AU  - N. A. Bazhenov
TI  - Automatic structures and the theory of lists
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2015
SP  - 714
EP  - 722
VL  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2015_12_a22/
LA  - en
ID  - SEMR_2015_12_a22
ER  - 
%0 Journal Article
%A N. A. Bazhenov
%T Automatic structures and the theory of lists
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2015
%P 714-722
%V 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2015_12_a22/
%G en
%F SEMR_2015_12_a22
N. A. Bazhenov. Automatic structures and the theory of lists. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 12 (2015), pp. 714-722. http://geodesic.mathdoc.fr/item/SEMR_2015_12_a22/