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. 
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/
@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},
     year = {2016},
     volume = {28},
     number = {4},
     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
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
%U http://geodesic.mathdoc.fr/item/DM_2016_28_4_a7/
%G ru
%F 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