Equivalence problems for deterministic context-free languages and monadic recursion schemes
From MaRDI portal
Publication:1238426
DOI10.1016/S0022-0000(77)80019-6zbMath0358.68109OpenAlexW2009721064MaRDI QIDQ1238426
Publication date: 1977
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(77)80019-6
Related Items (22)
The Hoare Logic of Deterministic and Nondeterministic Monadic Recursion Schemes ⋮ An axiomatic approach to the Korenjak-Hopcroft algorithms ⋮ Algorithm for verifying the equivalence of linear unary recursive programs on ordered semigroup scales ⋮ A subclass of deterministic context-free languages with a decidable inclusion problem ⋮ Superdeterministic DPDAs: The method of accepting does affect decision problems ⋮ A representation of trees by languages. II ⋮ Decidable subcases of the equivalence problem for recursive program schemes ⋮ The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine ⋮ DPDA's in 'Atomic normal form' and applications to equivalence problems ⋮ New techniques for proving the decidability of equivalence problem ⋮ Unnamed Item ⋮ Infinite trees in normal form and recursive equations having a unique solution ⋮ Simple context-free languages and free monadic recursion schemes ⋮ Normal forms of deterministic grammars ⋮ A representation of trees by languages. I ⋮ On equivalence and subclass containment problems for deterministic context-free languages ⋮ Monadic recursion schemes: The effect of constants ⋮ Decidability of the equivalence problem for deterministic pushdown automata ⋮ The complexity of monadic recursion schemes: executability problems, nesting depth, and applications ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ The complexity of monadic recursion schemes: Exponential time bounds ⋮ On the Decidability of the Equivalence Problem for Monadic Recursive Programs
Cites Work
This page was built for publication: Equivalence problems for deterministic context-free languages and monadic recursion schemes
