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