The tree equivalence of linear recursion schemes

✍ Scribed by V. Sabelfeld

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 206 KB
• Volume: 238
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00207-2

✦ Synopsis

In the paper, a complete system of transformation rules preserving the tree equivalence and a polynomial-time algorithm deciding the tree equivalence of linear polyadic recursion schemes are proposed. The algorithm is formulated as a sequential transformation process which brings together the schemes in question. In the last step, the tree equivalence problem for the given schemes is reduced to a global ow analysis problem which is solved by an e cient marking algorithm.