A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars

DOI10.1016/0304-3975(83)90052-XzbMath0509.68072MaRDI QIDQ1838320

Etsuji Tomita

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

equivalencecontext-free grammarbranching algorithmGreibach normal formLL(k) grammarskippingstrict deterministic grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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