A fast algorithm for constructing a tree automaton recognizing a congruential tree language (Q1261478): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:37, 31 January 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