The equivalence problem for real-time strict deterministic languages

DOI10.1016/S0019-9958(80)90887-6zbMath0444.68038MaRDI QIDQ3888532

Namio Honda, Yasuyoshi Inagaki, Michio Oyamaguchi

Publication date: 1980

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

deterministic pushdown automataequivalence problemreal-time strict deterministic languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (29)

An axiomatic approach to the Korenjak-Hopcroft algorithms ⋮ The equivalence and inclusion problems for NTS languages ⋮ NTS languages are deterministic and congruential ⋮ An approach to deciding the observational equivalence of Algol-like languages ⋮ On some decision questions concerning pushdown machines ⋮ The equivalence problem for real-time strict deterministic pushdown automata ⋮ A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict ⋮ Superdeterministic DPDAs: The method of accepting does affect decision problems ⋮ The simultaneous accessibility of two configurations of two equivalent DPDA's ⋮ The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine ⋮ On the decidability of equivalence for deterministic pushdown transducers ⋮ DPDA's in 'Atomic normal form' and applications to equivalence problems ⋮ New techniques for proving the decidability of equivalence problem ⋮ A new class of C.F.L. for which the equivalence is decidable ⋮ The equivalence problem for LL- and LR-regular grammars ⋮ A hierarchy of real-time deterministic languages and their equivalence ⋮ Unnamed Item ⋮ Decidability of bisimulation equivalence for normed pushdown processes ⋮ The equivalence problem for real-time deterministic pushdown automata ⋮ Decidability of DPDA equivalence ⋮ Decidability of bisimulation equivalence for normed pushdown processes ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars ⋮ Constructing a realtime deterministic pushdown automaton from a grammar ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ Fundamental properties of infinite trees ⋮ Some negative results concerning DPDA's ⋮ Some results on subclass containment problems for special classes of dpda's related to nonsingular machines ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata

This page was built for publication: The equivalence problem for real-time strict deterministic languages