Geodesic
The theory of Lists and $\Sigma$-definability
The Bulletin of Irkutsk State University. Series Mathematics, Tome 4 (2011) no. 4, pp. 27-38 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider two-sorted structures (lists algebras) consisting of a basic set $S$ and a set of lists $I_S$ (lists are ordered collections of elements from $S \cup I_S$) with natural relations and operations such as membership relation, head and tail operations etc. and show that recursively definable functions are $\Sigma$-definable in the lists algebras. The recursion is on the length and depth of a list.
Keywords: theory of lists, $\Sigma$-definability, recursion theorem. 
@article{IIGUM_2011_4_4_a2,
     author = {A. A. Gavryushkina},
     title = {The theory of {Lists} and $\Sigma$-definability},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {27--38},
     year = {2011},
     volume = {4},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2011_4_4_a2/}
}
TY  - JOUR
AU  - A. A. Gavryushkina
TI  - The theory of Lists and $\Sigma$-definability
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2011
SP  - 27
EP  - 38
VL  - 4
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2011_4_4_a2/
LA  - ru
ID  - IIGUM_2011_4_4_a2
ER  - 
%0 Journal Article
%A A. A. Gavryushkina
%T The theory of Lists and $\Sigma$-definability
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2011
%P 27-38
%V 4
%N 4
%U http://geodesic.mathdoc.fr/item/IIGUM_2011_4_4_a2/
%G ru
%F IIGUM_2011_4_4_a2
A. A. Gavryushkina. The theory of Lists and $\Sigma$-definability. The Bulletin of Irkutsk State University. Series Mathematics, Tome 4 (2011) no. 4, pp. 27-38. http://geodesic.mathdoc.fr/item/IIGUM_2011_4_4_a2/

[1] S. S. Goncharov, “Zamechanie ob aksiomakh spisochnoi nadstroiki GES”, Logicheskie voprosy teorii tipov dannykh, Vychislitelnye sistemy, 114, Novosibirsk, 1986, 11–15 | MR | Zbl

[2] S. S. Goncharov, D. I. Sviridenko, “$\Sigma$-programmirovanie”, Logiko-matematicheskie problemy MOZ, Vychislitelnye sistemy, 107, Novosibirsk, 1985, 3–29 | MR | Zbl

[3] Yu. L. Ershov, Opredelimost i vychislimost, Sibirskaya shkola algebry i logiki, Nauchnaya kniga, Novosibirsk, 1996 | MR | Zbl

[4] Yu. L. Ershov, E. A. Palyutin, Matematicheskaya logika, Lan, SPb., 2004

[5] A. A. Malykh, A. V. Mantsivoda, V. S. Ulyanov, “Logicheskie arkhitektury i ob'ektno-orientirovannyi podkhod”, Vestnik NGU. Ser. Matematika, mekhanika, informatika, 9:3 (2009), 64–85 | Zbl

[6] A. A. Malykh, A. V. Mantsivoda, “Ob'ektno-orientirovannaya deskriptivnaya logika”, Izv. Irkut. gos. un-ta. Ser. Matematika, 4:1 (2011), 57–72 | MR | Zbl

[7] J. Barwise, Admissible Sets and Structures, Perspectives in Mathematical Logic, Springer-Verlag, Berlin–Heidelberg–New York, 1975 | DOI | MR | Zbl

[8] Yu. L. Ershov, S. S. Goncharov, D. I. Sviridenko, “Semantic Programming”, Information processing, Proc. IFIP 10th World Comput. Congress (Dublin, 1986), v. 10, 1093–1100 | MR