Geodesic
On the complexity of the computation of rudimentary predicates
Diskretnaya Matematika, Tome 12 (2000) no. 4, pp. 83-98.

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

The class of rudimentary predicates is defined as the minimal class of numerical predicates which contains the equality and concatenation predicates and is closed with respect to the propositional logic operations, the explicit transformations, and the bounded quantification. The complexity of computation of rudimentary predicates is defined in terms of alternating Turing machines with a finite number of alternations. Polynomial computability of rudimentary $\exists$- and $\forall$-predicates by deterministic Turing machine is proved. Hierarchies $\{R\Sigma_k\}$ and $\{R\Pi_k\}$ of the rudimentary predicate class are defined. The class $R\Sigma_1\cap R\Pi_1$ is analysed. Unsolvability of the non-emptiness problem for the class $R\Pi_1$ is proved. The research was supported by the Russian Foundation for Basic Research, grant 00–01–00351. 
@article{DM_2000_12_4_a6,
     author = {S. S. Marchenkov},
     title = {On the complexity of the computation of rudimentary predicates},
     journal = {Diskretnaya Matematika},
     pages = {83--98},
     publisher = {mathdoc},
     volume = {12},
     number = {4},
     year = {2000},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2000_12_4_a6/}
}
TY  - JOUR
AU  - S. S. Marchenkov
TI  - On the complexity of the computation of rudimentary predicates
JO  - Diskretnaya Matematika
PY  - 2000
SP  - 83
EP  - 98
VL  - 12
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2000_12_4_a6/
LA  - ru
ID  - DM_2000_12_4_a6
ER  - 
%0 Journal Article
%A S. S. Marchenkov
%T On the complexity of the computation of rudimentary predicates
%J Diskretnaya Matematika
%D 2000
%P 83-98
%V 12
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2000_12_4_a6/
%G ru
%F DM_2000_12_4_a6
S. S. Marchenkov. On the complexity of the computation of rudimentary predicates. Diskretnaya Matematika, Tome 12 (2000) no. 4, pp. 83-98. http://geodesic.mathdoc.fr/item/DM_2000_12_4_a6/

[1] Kuznetsov A. V., “K teoreme o kanonicheskoi forme dlya ordinalno-rekursivnykh funktsii”, Gudstein R. L., Matematicheskaya logika, IL, Moskva, 1961, 149–154

[2] Smalyan R., Teoriya formalnykh sistem, Nauka, Moskva, 1981 | MR

[3] Nepomnyaschii V. A., “Rudimentarnye predikaty i tyuringovy vychisleniya”, Dokl. AN SSSR, 195:2 (1970), 282–284 | MR | Zbl

[4] Nepomnyaschii V. A., “Rudimentarnaya interpretatsiya dvulentochnykh tyuringovykh vychislenii”, Kibernetika, 1970, no. 2, 29–35 | Zbl

[5] Nepomnyaschii V. A., “Rudimentarnoe modelirovanie nedeterminirovannykh tyuringovykh vychislenii”, Kibernetika, 1973, no. 2, 23–29 | Zbl

[6] Chandra A. K., Dexter C. K., Stockmeyer L. J., “Alternation”, J. ACM, 28:1 (1981), 114–133 | DOI | MR | Zbl

[7] Maltsev A. I., Algoritmy i rekursivnye funktsii, Nauka, Moskva, 1986 | MR

[8] Marchenkov S. S., “O predstavlenii slovarnykh predikatov iz arifmeticheskoi ierarkhii”, Diskretnaya matematika, 2:1 (1990), 87–93 | MR | Zbl

[9] Marchenkov S. S., “Nerazreshimost pozitivnoi $\forall\exists$-teorii svobodnoi polugruppy”, Sibirskii matem. zhurnal, 23:1 (1982), 196–198 | MR | Zbl