MINIMAL EQUATIONAL REPRESENTATIONS OF RECOGNIZABLE TREE-LANGUAGES

A tree language is congruential if it is the union of finitely many cl asses of a finitely generated congruence on the term algebra. It is we ll known that congruential tree languages are the same as recognizable tree languages. An equational representation is an ordered pair (E, P ), where E is either a ground term equation system or a ground term re writing system, and P is a finite set of ground terms. We say that (E, P) represents the congruential tree language L which is the union of those [GRAPHICS] classes containing an element of P, i.e., for which [ GRAPHICS] We define two sorts of minimality for equational representat ions. We introduce the cardinality vector (\E\, \P\) of an equational representation (E,P). Let less than or equal to(l) and less than or eq ual to(a) denote the lexicographic and antilexicographic orders on the set of ordered pairs of nonnegative integers, respectively. Let L be a congruential tree language. An equational representation (E, P) of L with less than or equal to(l)-minimal (less than or equal to(a)-minim al) cardinality vector is called less than or equal to(l)-minimal (les s than or equal to(a)-minimal). We compute, for an L given by a determ inistic bottom-up tree automaton, both a less than or equal to(l)-mini mal and a less than or equal to(a)-minimal equational representation o f L.