On the Decidability of the Equivalence Problem for Monadic Recursive Programs

DOI10.1051/ITA:2000112MaRDI QIDQ4508638zbMATH OpenOpenAlexFDO

Authors Vladimir A. Zakharov

Publication date 3 October 2000

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/222080, https://semanticscholar.org/paper/ad9d66164bee511fdc10f1717d665d40a6a598c8

zbMATH Keywords

deterministic monadic linear recursive programs

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the effective solvability of the problem of the equivalence of linear unary recursive programs.
• scientific article; zbMATH DE number 6387492
• Algorithm for verifying the equivalence of linear unary recursive programs on ordered semigroup scales
• Decidable subcases of the equivalence problem for recursive program schemes
• On the decidability of the equivalence problem for orthogonal sequential programs

Cites work

• scientific article; zbMATH DE number 3131416 (Why is no real title available?)
• scientific article; zbMATH DE number 4083010 (Why is no real title available?)
• scientific article; zbMATH DE number 1142319 (Why is no real title available?)
• scientific article; zbMATH DE number 2102750 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• An algorithm deciding functional equivalence in a new class of program schemes
• Classes of Recursively Enumerable Sets and Their Decision Problems
• Decidable Properties of Monadic Functional Schemas
• Decidable problems for powerful programs
• Deterministic one-counter automata
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• On Ianov's Program Schemata
• On formalised computer programs
• Program schemes, recursion schemes, and formal languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• The Complexity of the Equivalence Problem for Simple Programs
• The equivalence problem of multitape finite automata
• The extended equivalence problem for a class of non-real-time deterministic pushdown automata
• Tree equivalence of linear recursive schemata is polynomial-time decidable

Cited in

(13)

• On the decidability of the equivalence problem for orthogonal sequential programs
• On the effective solvability of the problem of the equivalence of linear unary recursive programs.
• scientific article; zbMATH DE number 1738658 (Why is no real title available?)
• Using algebraic models of programs for detecting metamorphic malwares
• Algorithms for equivalence and reduction to minimal form for a class of simple recursive equations
• The Hoare logic of deterministic and nondeterministic monadic recursion schemes
• Program equivalence checking by two-tape automata
• Decidability of equivalence in the set of program schema with monotonic and partially commutative operators
• scientific article; zbMATH DE number 6387492 (Why is no real title available?)
• scientific article; zbMATH DE number 4097355 (Why is no real title available?)
• A short proof of the decidability of normalization in recursive program schemes
• Decidable properties of monadic recursive schemas with a depth parameter
• On the Hoare theory of monadic recursion schemes

This page was built for publication: On the Decidability of the Equivalence Problem for Monadic Recursive Programs

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