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

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

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},
     publisher = {mathdoc},
     volume = {277},
     year = {2001},
     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
PB  - mathdoc
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
%I mathdoc
%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/