A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars
From MaRDI portal
Publication:1838320
DOI10.1016/0304-3975(83)90052-XzbMath0509.68072MaRDI QIDQ1838320
Publication date: 1983
Published in: Theoretical Computer Science (Search for Journal in Brave)
equivalencecontext-free grammarbranching algorithmGreibach normal formLL(k) grammarskippingstrict deterministic grammar
Related Items (4)
The extended equivalence problem for a class of non-real-time deterministic pushdown automata ⋮ New techniques for proving the decidability of equivalence problem ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata
Cites Work
- Unnamed Item
- Unnamed Item
- Superdeterministic DPDAs: The method of accepting does affect decision problems
- 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
- Two decidability results for deterministic pushdown automata
- On equivalence of grammars through transformation trees
- Strict deterministic grammars
- Optimization of LR(k) parsers
- 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
- The equivalence problem for real-time strict deterministic languages
- On the Parsing of Deterministic Languages
- 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
This page was built for publication: A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars
