A Learning Algorithm for a Subclass of Tree Rewriting Systems

Tree replacement / rewriting systems are an interesting model of computation. They are used in theorem proving, algebraic simplification, and language theory. A fundamental property of tree replacement systems is the Church-Rosser property, which expresses the fact that interconvertability of two trees can be checked by mere simplification to a common tree. In this paper, we give a learning algorithm for a subclass of the class of Church-Rosser tree replacement systems.