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/

[1] D. J. Moore, B. Russell, “Axiomatic Data Type Specifications: a First Order Theory of Linear Lists”, Acta Informatica, 15:3 (1981), 193–207 | MR

[2] S. S. Goncharov, “A Theory of Lists and Its Models”, Vychisl. Sistemy, 114 (1986), 84–95 (In Russian) | MR

[3] J. R. Büchi, “Weak Second-Order Arithmetic and Finite Automata”, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 6 (1960), 66–92 | MR

[4] J. R. Büchi, “On a Decision Method in Restricted Second Order Arithmetic”, Proc. Internat. Congr. on Logic, Methodology and Philosophy of Science (1960), Stanford Univ. Press, Stanford, 1962, 1–11 | MR

[5] M. O. Rabin, “Decidability of Second-Order Theories and Automata on Infinite Trees”, Transactions of the American Mathematical Society, 141 (1969), 1–35 | MR

[6] B. Khoussainov, A. Nerode, “Automatic Presentations of Structures”, Logic and Computational Complexity, Lecture Notes in Computer Science, 960, Springer, Berlin, 1995, 367–392 | MR

[7] B. Khoussainov, A. Nerode, “Open Questions in the Theory of Automatic Structures”, Bulletin of the EATCS, 94 (2008), 181–204 | MR

[8] S. Rubin, “Automata Presenting Structures: a Survey of the Finite String Case”, Bulletin of Symbolic Logic, 14:2 (2008), 169–209 | MR

[9] B. Khoussainov, M. Minnes, “Three Lectures on Automatic Structures”, Logic Colloquium (2007), Lecture Notes in Logic, 35, Assoc. Symbol. Logic, La Jolla, 2010, 132–176 | MR

[10] D. Kuske, J. Liu, M. Lohrey, “The Isomorphism Problem on Classes of Automatic Structures with Transitive Relations”, Transactions of the American Mathematical Society, 365:10 (2013), 5103–5151 | MR

[11] O. Kharlampovich, B. Khoussainov, A. Miasnikov, “From Automatic Structures to Automatic Groups”, Groups, Geometry, and Dynamics, 8:1 (2014), 157–198 | MR

[12] Yu. L. Ershov, S. S. Goncharov, Constructive Models, Consultants Bureau, New York, 2000 | MR

[13] C. J. Ash, J. Knight, Computable Structures and Hyperarithmetical Hierarchy, North-Holland Publishing Co., Amsterdam, 2000 | MR

[14] Yu. L. Ershov, E. A. Palyutin, Mathematical Logic, Mir, M., 1984 | MR

[15] S. S. Goncharov, D. I. Sviridenko, “$\Sigma$-Programming”, Vychisl. Sistemy, 107 (1985), 3–29 (In Russian) | MR

[16] S. S. Goncharov, Yu. L. Ershov, D. I. Sviridenko, “Semantic Programming”, Information Processing 86, Proc. IFIP 10th World Comput. Congr., North-Holland, Amsterdam, 1986, 1113–1120 | MR

[17] A. A. Malykh, A. V. Mantsivoda, “List Superstructures and Semantics of Iterators”, Journal of Mathematical Sciences (New York), 203:4 (2014), 540–550 | MR

[18] M. V. Korovina, “Generalized Computability of Real Functions”, Siberian Advances in Mathematics, 2:4 (1992), 85–103 | MR

[19] M. V. Korovina, O. V. Kudinov, “A New Approach to the Computability of Real-Valued Functions”, Vychisl. Sistemy, 156 (1996), 3–23 (In Russian) | MR

[20] S. A. Aleksandrova, “The Uniformization Problem for $\Sigma$-Predicates in a Hereditarily Finite List Superstructure over the Real Exponential Field”, Algebra and Logic, 53:1 (2014), 1–8 | MR

[21] J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Boston, 2000 | MR

[22] A. Blumensath, E. Grädel, “Automatic Structures”, Proc. 15th Ann. IEEE Symp. Logic Comp Sci., IEEE Comp. Soc. Press, Los-Alamitos, 2000, 51–62 | MR

[23] C. Delhommé, “Automacité des Ordinaux et des Graphes Homogènes”, C.R. Math. Acad. Sci. Paris, 339:1 (2004), 5–10 (In French) | MR

[24] B. Khoussainov, A. Nies, S. Rubin, F. Stephan, “Automatic Structures: Richness and Limitations”, Conference “Logic in Computer Science 2004”, Logical Methods in Computer Science, 2, no. 2, 2004, 18 pp. | MR

[25] B. Khoussainov, S. Rubin, F. Stephan, “Definability and Regularity in Automatic Structures”, STACS 2004, Lecture Notes in Computer Science, 2996, Springer, Berlin, 2004, 440–451 | MR