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

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