The equivalence problem for real-time DPDAs
From MaRDI portal
Publication:3777488
DOI10.1145/28869.28881zbMATH Open0637.68094OpenAlexW2048217963MaRDI QIDQ3777488FDOQ3777488
Authors: Michio Oyamaguchi 
Publication date: 1987
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/28869.28881
Recommendations
- The equivalence problem for deterministic pushdown automata is decidable
- Decidability of the equivalence problem for deterministic pushdown automata
- A weaker sufficient condition for the equivalence of a pair of DPDA's to be decidable
- scientific article; zbMATH DE number 2086674
- Decidability of the equivalence problem for synchronous deterministic pushdown-store automata
Cited In (18)
- The equivalence problem for deterministic pushdown automata is decidable
- \(L(A)=L(B)\)? decidability results from complete formal systems
- Title not available (Why is that?)
- A fast algorithm to decide on the equivalence of stateless DPDA
- Problems of inclusion and equivalence for program schemata and formal languages
- The extended equivalence problem for a class of non-real-time deterministic pushdown automata
- Title not available (Why is that?)
- An intermediate machine technique for deciding equivalence between a DPDA and a linear DPDA
- Equivalence of deterministic pushdown automata revisited
- Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
- Some decision problems about controlled rewriting systems
- New techniques for proving the decidability of equivalence problem
- Decidable subcases of the equivalence problem for recursive program schemes
- Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
- New families of non real time dpda's and their decidability results
- Decidability of the equivalence problem for synchronous deterministic pushdown-store automata
- Language equivalence of deterministic real-time one-counter automata is NL-complete
- \(L(A)=L(B)\)? A simplified decidability proof.
This page was built for publication: The equivalence problem for real-time DPDAs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3777488)
