Tree equivalence of linear recursive schemata is polynomial-time decidable

DOI10.1016/0020-0190(81)90046-6zbMath0479.68052OpenAlexW2049819904MaRDI QIDQ1162152

Viktor K. Sabelfeld

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90046-6

zbMATH Keywords

recursive schemefunction callequivalence problemequivalence over interpretationsglobal flow analysis problemmarking algorithmrecognizing algorithm

Mathematics Subject Classification ID

Related Items (3)

The tree equivalence of linear recursion schemes ⋮ Some equivalent transformations of recursive programs based on their schematic properties ⋮ On the Decidability of the Equivalence Problem for Monadic Recursive Programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing in systems described by equations
• The logic-termal equivalence is polynomial-time decidable
• DPDA's in 'Atomic normal form' and applications to equivalence problems
• Program equivalence and context-free grammars
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• On jump-deterministic pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata

This page was built for publication: Tree equivalence of linear recursive schemata is polynomial-time decidable