Decidable Properties of Monadic Functional Schemas

DOI10.1145/321765.321780zbMath0289.68036OpenAlexW2028140996MaRDI QIDQ4041106

Amir Pnueli, Zohar Manna, E. A. Ashcroft

Publication date: 1973

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321765.321780

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (18)

Algorithm for verifying the equivalence of linear unary recursive programs on ordered semigroup scales ⋮ Programs as partial graphs. I: Flow equivalence and correctness ⋮ Programs as partial graphs. II: Recursion ⋮ Program equivalence checking by two-tape automata ⋮ Simple context-free languages and free monadic recursion schemes ⋮ Program equivalence and context-free grammars ⋮ The inclusion problem for simple languages ⋮ On the completeness of the inductive assertion method ⋮ Equivalence problems for deterministic context-free languages and monadic recursion schemes ⋮ A direct algorithm for checking equivalence of LL(k) grammars ⋮ An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines ⋮ IO and OI. I ⋮ IO and OI. II ⋮ On some classes of interpretations ⋮ Monadic recursion schemes: The effect of constants ⋮ The complexity of monadic recursion schemes: executability problems, nesting depth, and applications ⋮ The complexity of monadic recursion schemes: Exponential time bounds ⋮ On the Decidability of the Equivalence Problem for Monadic Recursive Programs

This page was built for publication: Decidable Properties of Monadic Functional Schemas