A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict

DOI10.1016/0304-3975(89)90096-0zbMath0678.68076OpenAlexW2031096385MaRDI QIDQ1124364

Etsuji Tomita, Kazushi Seino

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90096-0

zbMATH Keywords

branching algorithmequivalence of two deterministic pushdown transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithms in computer science (68W99)

Related Items (5)

Equivalence of Linear Tree Transducers with Output in the Free Group ⋮ The extended equivalence problem for a class of non-real-time deterministic pushdown automata ⋮ Nivat's theorem for pushdown transducers ⋮ On transductions of formal power series over complete semirings ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems

Cites Work

• On some decision questions concerning pushdown machines
• An extended direct branching algorithm for checking equivalence of deterministic pushdown automata
• A weaker sufficient condition for the equivalence of a pair of DPDA's to be decidable
• On the decidability of equivalence for deterministic pushdown transducers
• Synchronizable deterministic pushdown automata and the decidability of their equivalence
• A direct branching algorithm for checking equivalence of some classes of deterministic pushdown automata
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• The equivalence problem for real-time strict deterministic languages

This page was built for publication: A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict