Geodesic
Bounded prefix concatenation operation and finite bases with respect to the superposition
Diskretnaya Matematika, Tome 28 (2016) no. 4, pp. 91-99.

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

The paper is concerned with word functions over the alphabet $\{1,2\}$. Given arbitrary one-place functions $f_1,\ldots,f_l$, the class BPC$[f_1,\ldots,f_l]$ is defined as the closure of the set of simplest word functions and the functions $f_1,\ldots,f_l$ under the operations of superposition and bounded prefix concatenation. The class BPC$[f_1,\ldots,f_l]$ is shown to have a finite basis with respect to the superposition.
Keywords: operation of bounded prefix concatenation, finite basis with respect to the superposition. 
@article{DM_2016_28_4_a7,
     author = {S. S. Marchenkov},
     title = {Bounded prefix concatenation operation and finite bases with respect to the superposition},
     journal = {Diskretnaya Matematika},
     pages = {91--99},
     publisher = {mathdoc},
     volume = {28},
     number = {4},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_4_a7/}
}
TY  - JOUR
AU  - S. S. Marchenkov
TI  - Bounded prefix concatenation operation and finite bases with respect to the superposition
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 91
EP  - 99
VL  - 28
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_4_a7/
LA  - ru
ID  - DM_2016_28_4_a7
ER  - 
%0 Journal Article
%A S. S. Marchenkov
%T Bounded prefix concatenation operation and finite bases with respect to the superposition
%J Diskretnaya Matematika
%D 2016
%P 91-99
%V 28
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2016_28_4_a7/
%G ru
%F DM_2016_28_4_a7
S. S. Marchenkov. Bounded prefix concatenation operation and finite bases with respect to the superposition. Diskretnaya Matematika, Tome 28 (2016) no. 4, pp. 91-99. http://geodesic.mathdoc.fr/item/DM_2016_28_4_a7/

[1] Volkov S. A., “Primer prostoi kvaziuniversalnoi funktsii v klasse ${\cal E}^2$ ierarkhii Gzhegorchika”, Diskretnaya matematika, 18:4 (2006), 31–44 | DOI | Zbl

[2] Maltsev A. I., “Iterativnye algebry i mnogoobraziya Posta”, Algebra i logika, 5:2 (1966), 5–24 | MR | Zbl

[3] Maltsev A. I., Iterativnye algebry Posta, Izdatelstvo NGU, Novosibirsk, 1976, 100 pp. | MR

[4] Marchenkov S. S., “Ustranenie skhem rekursii v klasse ${\cal E}^2$ Gzhegorchika”, Matem. zametki, 5:5 (1969), 561–568

[5] Marchenkov S. S., “Ob ogranichennykh rekursiyakh”, Mathematica Balkanica, 2 (1972), 124–142 | MR

[6] Marchenkov S. S., “Ob odnom bazise po superpozitsii v klasse funktsii, elementarnykh po Kalmaru”, Matem. zametki, 27:3 (1980), 321–332 | MR | Zbl

[7] Marchenkov S. S., “Prostye primery bazisov po superpozitsii v klasse funktsii, elementarnykh po Kalmaru”, Combinatorics and Graph Theory, Banach Cent. Publ., 25, Warsaw, 1989, 119–126 | MR | Zbl

[8] Marchenkov S. S., “Bazisy po superpozitsii v klassakh rekursivnykh funktsii”, Matem. voprosy kibernetiki, 3 (1991), 115–139 | MR | Zbl

[9] Marchenkov S. S., Elementarnye rekursivnye funktsii, MTsNMO, M., 2003, 112 pp.

[10] Marchenkov S. S., “Superpozitsii elementarnykh arifmeticheskikh funktsii”, Diskretn. analiz i issled. operatsii. Seriya 1, 13:4 (2006), 33–48 | Zbl

[11] Marchenkov S. S., “Ob elementarnykh slovarnykh funktsiyakh, poluchaemykh na osnove ogranichennoi prefiksnoi konkatenatsii”, Diskretnaya matematika, 27:3 (2015), 44–55 ; Marchenkov S. S., “On elementary word functions obtained by bounded prefix concatenation”, Discrete Math. Appl., 26:3 (2016), 155–163 | DOI | DOI | MR | Zbl

[12] Grzegorczyk A., “Some classes of recursive functions”, Rozprawy Matematiczne, 4 (1953), 1–46 | MR

[13] Parsons Ch., “Hierarchies of primitive recursive functions”, Zeitschr. Math. Logik Grundlag. Math., 14:4 (1968), 357–376 | DOI | MR | Zbl

[14] Rödding D., “Über die Eliminierbarkeit von Definitionsschemata in der Theorie der rekursiven Funktionen”, Zeitschr. Math. Logik Grundlag. Math., 10:4 (1964), 315–330 | DOI | MR | Zbl