A fast algorithm for constructing a tree automaton recognizing a congruential tree language (Q1261478): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q591314 |
||
Property / reviewed by | |||
Property / reviewed by: Magnus Steinby / rank | |||
Revision as of 07:19, 20 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A fast algorithm for constructing a tree automaton recognizing a congruential tree language |
scientific article |
Statements
A fast algorithm for constructing a tree automaton recognizing a congruential tree language (English)
0 references
3 October 1993
0 references
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.
0 references
term rewriting
0 references
tree automata
0 references
tree languages
0 references