Minimal equational representations of recognizable tree languages

A tree language is congruential if it is the union of finitely many classes of a finitely generated congruence on the term algebra. It is well 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 rewriting 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 representations. We introduce the cardinality vector (\E\, \P\) of an equational representation (E,P). Let less than or equal to(l) and less than or equal 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)-minimal) cardinality vector is called less than or equal to(l)-minimal (less than or equal to(a)-minimal). We compute, for an L given by a deterministic bottom-up tree automaton, both a less than or equal to(l)-minimal and a less than or equal to(a)-minimal equational representation of L.