A Decision Problem for Transformations of Trees

Abstract

For a given class of transformations on graphs there arises naturally the problem of deciding when one graph can be transformed into another by a finite sequence of such transformations. We consider, in this paper, the special case of this problem when the graphs are finite trees and the transformations consist of rearranging the order of the segments from a point and replacing subtrees by other trees according to a given set of pairs of interchangeable trees. This decision problem is, in fact, equivalent to the word problem for one-generator algebras in a certain variety of algebraic systems and we exhibit a procedure for solving the word problem for these algebras.