The tree equivalence of linear recursion schemes

DOI10.1016/S0304-3975(98)00207-2MaRDI QIDQ1575234zbMATH OpenOpenAlexFDO

Authors Viktor K. Sabelfeld

Publication date 21 August 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(98)00207-2, https://publikationen.bibliothek.kit.edu/34352000

zbMATH Keywords

recursion schemestransformation rulestree equivalence

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Grammars and rewriting systems (68Q42)

Recommendations

• Equivalent transformations of recursive schemes with finite deconvolution
• Decidable subcases of the equivalence problem for recursive program schemes
• Regular algebra of functionals of labeled trees
• Deciding equivalence of linear tree-to-word transducers in polynomial time
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars

Cites work

• A representation of trees by languages. I
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• DPDA's in 'Atomic normal form' and applications to equivalence problems
• scientific article; zbMATH DE number 3576680 (Why is no real title available?)
• Monotone data flow analysis frameworks
• On jump-deterministic pushdown automata
• Program equivalence and context-free grammars
• The equivalence problem for deterministic finite-turn pushdown automata
• Tree equivalence of linear recursive schemata is polynomial-time decidable
• Variations on the Common Subexpression Problem

Cited in

(3)

• Recursion on Homogeneous Trees
• Regular algebra of functionals of labeled trees
• Equivalent transformations of recursive schemes with finite deconvolution

This page was built for publication: The tree equivalence of linear recursion schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1575234)