KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
§
Volltext
URN: urn:nbn:de:swb:90-AAA343520008

The tree equivalence of linear recursion schemes

Sabelfeld, Viktor

Abstract:

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 flow
analysis problem which is solved by an efficient marking
algorithm.


Zugehörige Institution(en) am KIT Institut für Rechnerentwurf und Fehlertoleranz (IRF)
Publikationstyp Zeitschriftenaufsatz
Jahr 2000
Sprache Englisch
Identifikator KITopen-ID: 34352000
Erscheinungsvermerk Theor. comput. sci. 238 (2000) H. 1 S. 1-29.
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page