An extended direct branching algorithm for checking equivalence of deterministic pushdown automata
From MaRDI portal
Publication:801689
DOI10.1016/0304-3975(84)90026-4zbMath0552.68065OpenAlexW2059683551MaRDI QIDQ801689
Publication date: 1984
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(84)90026-4
Related Items
A fast algorithm to decide on the equivalence of stateless DPDA, The extended equivalence problem for a class of non-real-time deterministic pushdown automata, Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines, A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict, A weaker sufficient condition for the equivalence of a pair of DPDA's to be decidable
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- A hierarchy of real-time deterministic languages and their equivalence
- Deterministic one-counter automata
- A result on the equivalence problem for deterministic pushdown automata
- A direct algorithm for checking equivalence of LL(k) grammars
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- A representation of trees by languages. I
- Two decidability results for deterministic pushdown automata
- On equivalence of grammars through transformation trees
- A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars
- A direct branching algorithm for checking equivalence of some classes of deterministic pushdown automata
- Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
- An axiomatic approach to the Korenjak-Hopcroft algorithms
- The equivalence problem for real-time strict deterministic languages
- The equivalence problem for some non-real-time deterministic pushdown automata
- A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors
- Some remarks on the KH algorithm fors-grammars
- The decidability of equivalence for deterministic stateless pushdown automata
- The equivalence problem for deterministic finite-turn pushdown automata
- Properties of deterministic top-down grammars
- Real-Time Strict Deterministic Languages
