Geodesic
Effective algorithm for construction of terms of minimum computational complexity
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2016), pp. 21-33 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of construction of terms of the minimum computational complexity by the program which contains only assignments and a finite number of variables, and operating on the free one-generated gruppoide with the signature consisting of a binary operation symbol and one generating element is considered. Such terms are considered that leaves of the corresponding full binary trees are labeled by pairwise different subterms. The effective algorithm of such construction is given and it is proved that for any natural $m$ it is possible to construct a term of height $h$ with $h-m$ variables.
Keywords: binary tree, computational complexity, the one-generated groupoide, assignment, effective algorithm.
Mots-clés : variable, term 
@article{VTPMK_2016_4_a1,
     author = {D. O. Daderkin},
     title = {Effective algorithm for construction of terms of minimum computational complexity},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {21--33},
     year = {2016},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2016_4_a1/}
}
TY  - JOUR
AU  - D. O. Daderkin
TI  - Effective algorithm for construction of terms of minimum computational complexity
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2016
SP  - 21
EP  - 33
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2016_4_a1/
LA  - ru
ID  - VTPMK_2016_4_a1
ER  - 
%0 Journal Article
%A D. O. Daderkin
%T Effective algorithm for construction of terms of minimum computational complexity
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2016
%P 21-33
%N 4
%U http://geodesic.mathdoc.fr/item/VTPMK_2016_4_a1/
%G ru
%F VTPMK_2016_4_a1
D. O. Daderkin. Effective algorithm for construction of terms of minimum computational complexity. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2016), pp. 21-33. http://geodesic.mathdoc.fr/item/VTPMK_2016_4_a1/

[1] Tiuryn J., “Implicit definability of finite binary trees by sets of equations”, Logic and Machines: Decision Problems and Complexity, Springer, Berlin Heidelberg, 1984, 320–332 | DOI | MR

[2] Kfoury A. I., “The pebble game and logic of programmes”, Harrey Friedmans Research on the Foundations of Mathematics, North-Holland, 1985, 317–329 | DOI | MR

[3] Musikaev I. Kh., Taitslin M. A., “About dynamic theories of free algebras”, Matematicheskii sbornik, 180:3 (1989), 307–321 (in Russian) | Zbl