A fast algorithm for constructing a tree automaton recognizing a congruential tree language (Q1261478): Difference between revisions

A tree language over a ranked alphabet \(\Sigma\) is congruential if it is the union of finitely many congruence classes of a finitely generated congruence of the \(\Sigma\)-term algebra. Hence a congruential \(\Sigma\)- tree language can be defined by giving a finite set of ground equations (which generate the congruence) and a finite number of \(\Sigma\)-trees (which specify the congruence classes). On the other hand, it is known that the congruential tree languages are exactly the recognizable tree languages. The author combines some earlier algorithms to yield an algorithm which in \(O(n\log n)\) time produces a tree recognizer for a congruential tree language given by a specification of size \(n\) of the kind mentioned above.