Equivalence problems for deterministic context-free languages and monadic recursion schemes

DOI10.1016/S0022-0000(77)80019-6MaRDI QIDQ1238426zbMATH OpenOpenAlexFDO

Authors Emily P. Friedman

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• Decidable Properties of Monadic Functional Schemas
• Deterministic context free languages
• scientific article; zbMATH DE number 3490487 (Why is no real title available?)
• scientific article; zbMATH DE number 3576680 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• Real-Time Definable Languages
• Strict deterministic grammars

Cited in

(22)

• 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
• Algorithm for verifying the equivalence of linear unary recursive programs on ordered semigroup scales
• scientific article; zbMATH DE number 3896271 (Why is no real title available?)
• 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
• On the Decidability of the Equivalence Problem for Monadic Recursive Programs
• The Hoare logic of deterministic and nondeterministic monadic recursion schemes
• 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

This page was built for publication: Equivalence problems for deterministic context-free languages and monadic recursion schemes

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