Geodesic
Upper bounds on the height of terms in the solution of the semiunification problem
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VI, Tome 277 (2001), pp. 53-79
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

In this paper we investigate on one decidable case of term semiunification problem, namely when all the functional symbols in the given terms have arity one, except, possibly, for outer symbols of terms, which have no restrictions. We propose an algorithm that builds a most general solution of the semiunification problem, and prove an upper bound on the height of this solution; the upper bound is linear by the height of terms in the given problem. Our method is to reduce the problem for terms to a special system of equations in free semigroups, and then to solve this system. 
@article{ZNSL_2001_277_a3,
     author = {V. B. Zhizhkun},
     title = {Upper bounds on the height of terms in the solution of the semiunification problem},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {53--79},
     year = {2001},
     volume = {277},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a3/}
}
TY  - JOUR
AU  - V. B. Zhizhkun
TI  - Upper bounds on the height of terms in the solution of the semiunification problem
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2001
SP  - 53
EP  - 79
VL  - 277
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a3/
LA  - ru
ID  - ZNSL_2001_277_a3
ER  - 
%0 Journal Article
%A V. B. Zhizhkun
%T Upper bounds on the height of terms in the solution of the semiunification problem
%J Zapiski Nauchnykh Seminarov POMI
%D 2001
%P 53-79
%V 277
%U http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a3/
%G ru
%F ZNSL_2001_277_a3
V. B. Zhizhkun. Upper bounds on the height of terms in the solution of the semiunification problem. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VI, Tome 277 (2001), pp. 53-79. http://geodesic.mathdoc.fr/item/ZNSL_2001_277_a3/