On the decidability of equivalence for deterministic pushdown transducers

DOI10.1016/0020-0190(81)90116-2zbMath0473.68077OpenAlexW1982755473MaRDI QIDQ1158772

Louis E. Rosier, Oscar H. Ibarra

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90116-2

zbMATH Keywords

alternate stacking

Mathematics Subject Classification ID

Related Items (6)

An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines ⋮ A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict ⋮ Equivalence of simple functions ⋮ New techniques for proving the decidability of equivalence problem ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superdeterministic DPDAs: The method of accepting does affect decision problems
• Deterministic one-counter automata
• A result on the equivalence problem for deterministic pushdown automata
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• Two decidability results for deterministic pushdown automata
• Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
• The equivalence problem for real-time strict deterministic languages
• Superdeterministic PDAs
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Tape bounds for some subclasses of deterministic context-free languages
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata
• The theory of languages

This page was built for publication: On the decidability of equivalence for deterministic pushdown transducers