History

Please fill in your query. A complete syntax description you will find on the General Help page.
Regular algebra of functionals of labeled trees. (English)
Cybernetics 21, 591-598 (1985); translation from Kibernetika 1985, No.5, 25-30 (1985).
Algorithmic problems of program schema comparison are known to be equivalent to the corresponding problems for schemas on free interpretations [{\it S. J. Garland} and {\it D. C. Luckham}, J. Comput. Syst. Sci. 7, 119-160 (1973; Zbl 0277.68010)]. Comparison of program schemas therefore leads to analysis of transformers on labeled trees. In this article we construct a class of RL-transformers on labeled trees which corresponds to the class of RL-schemas on free interpretations. The class of RL-schemas is an algebra of schemas made up from linear unitary recursion schemas by a finite application of multiplication, $α$- disjunction, and $α$-iteration, as defined by {\it V. M. Glushkov} [Kibernetika 1965, No.5, 1-9 (1965; Zbl 0156.018)]. The problems of weak equivalence and inclusion are found to be decidable for RL-schemas. These results follow from the corresponding results for RL-transformers.