The equivalence problem for real-time DPDAs

DOI10.1145/28869.28881zbMath0637.68094OpenAlexW2048217963MaRDI QIDQ3777488

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

zbMATH Keywords

equivalence problemdeterministic real-time pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (11)

The extended equivalence problem for a class of non-real-time deterministic pushdown automata ⋮ Problems of inclusion and equivalence for program schemata and formal languages ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages ⋮ The equivalence problem for deterministic pushdown automata is decidable ⋮ Decidable subcases of the equivalence problem for recursive program schemes ⋮ Some decision problems about controlled rewriting systems ⋮ New techniques for proving the decidability of equivalence problem ⋮ Equivalence of deterministic pushdown automata revisited ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ \(L(A)=L(B)\)? A simplified decidability proof.

This page was built for publication: The equivalence problem for real-time DPDAs