The equivalence problem for real-time strict deterministic languages

DOI10.1016/S0019-9958(80)90887-6MaRDI QIDQ3888532zbMATH OpenFDO

Authors Michio Oyamaguchi, N. Honda, Yasuyoshi Inagaki

Publication date 1980

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

Full work available at URL https://doi.org/10.1016/S0019-9958(80)90887-6

zbMATH Keywords

deterministic pushdown automataequivalence problemreal-time strict deterministic languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited in

(29)

• Constructing a realtime deterministic pushdown automaton from a grammar
• 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
• The equivalence and inclusion problems for NTS languages
• NTS languages are deterministic and congruential
• 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
• 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
• Decidability of bisimulation equivalence for normed pushdown processes
• \(L(A)=L(B)\)? decidability results from complete formal systems
• Synchronizable deterministic pushdown automata and the decidability of their equivalence
• A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars
• An approach to deciding the observational equivalence of Algol-like languages
• The equivalence problem for real-time deterministic pushdown automata
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• scientific article; zbMATH DE number 3735179 (Why is no real title available?)
• The equivalence problem for real-time strict deterministic pushdown automata
• On some decision questions concerning pushdown machines
• Decidability of DPDA equivalence
• Decidability of bisimulation equivalence for normed pushdown processes
• An extended direct branching algorithm for checking equivalence of deterministic pushdown automata
• New techniques for proving the decidability of equivalence problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3888532)