Equivalence problems for deterministic context-free languages and monadic recursion schemes
From MaRDI portal
Publication:1238426
DOI10.1016/S0022-0000(77)80019-6zbMath0358.68109MaRDI QIDQ1238426
Publication date: 1977
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
68Q45: Formal languages and automata
Related Items
On the Decidability of the Equivalence Problem for Monadic Recursive Programs, The complexity of monadic recursion schemes: executability problems, nesting depth, and applications, The complexity of monadic recursion schemes: Exponential time bounds, New techniques for proving the decidability of equivalence problem, Superdeterministic DPDAs: The method of accepting does affect decision problems, A representation of trees by languages. II, 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, 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, \(L(A)=L(B)\)? decidability results from complete formal systems, Decidability of the equivalence problem for deterministic pushdown automata, Unnamed Item, An axiomatic approach to the Korenjak-Hopcroft algorithms, Decidable subcases of the equivalence problem for recursive program schemes, Infinite trees in normal form and recursive equations having a unique solution, A subclass of deterministic context-free languages with a decidable inclusion problem, Simple context-free languages and free monadic recursion schemes
Cites Work