Tree equivalence of linear recursive schemata is polynomial-time decidable

DOI10.1016/0020-0190(81)90046-6MaRDI QIDQ1162152zbMATH OpenOpenAlexFDO

Authors 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

function callequivalence problemrecursive schemeequivalence over interpretationsglobal flow analysis problemmarking algorithmrecognizing algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Decidability of theories and sets of sentences (03B25)

Cites work

• scientific article; zbMATH DE number 3485178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639170 (Why is no real title available?)
• scientific article; zbMATH DE number 3204690 (Why is no real title available?)
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• Computing in systems described by equations
• DPDA's in 'Atomic normal form' and applications to equivalence problems
• On jump-deterministic pushdown automata
• Program equivalence and context-free grammars
• The equivalence problem for deterministic finite-turn pushdown automata
• The logic-termal equivalence is polynomial-time decidable

Cited in

(4)

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

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

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