On equivalence of grammars through transformation trees

DOI10.1016/0304-3975(79)90024-0zbMath0409.68041OpenAlexW2028072917MaRDI QIDQ1259173

Ivan M. Havel, Amiram Yehudai, Michael A. Harrison

Publication date: 1979

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

Full work available at URL: https://doi.org/10.1016/0304-3975(79)90024-0

zbMATH Keywords

EquivalenceGrammar Oriented Decision ProcedureProblem for Deterministic Context-Free LanguagesStrict Deterministic GrammarsTransformation Trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (18)

An axiomatic approach to the Korenjak-Hopcroft algorithms ⋮ 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 ⋮ The equivalence problem for deterministic pushdown automata is decidable ⋮ Superdeterministic DPDAs: The method of accepting does affect decision problems ⋮ The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine ⋮ New techniques for proving the decidability of equivalence problem ⋮ Attribute grammars and recursive program schemes. I. II ⋮ The equivalence problem for LL- and LR-regular grammars ⋮ The inclusion problem for some subclasses of context-free languages ⋮ Decidability of DPDA equivalence ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ Complete formal systems for equivalence problems ⋮ A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ Fundamental properties of infinite trees ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata ⋮ \(L(A)=L(B)\)? A simplified decidability proof.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deterministic one-counter automata
• A result on the equivalence problem for deterministic pushdown automata
• The inclusion problem for simple languages
• Normal forms of deterministic grammars
• A direct algorithm for checking equivalence of LL(k) grammars
• Two decidability results for deterministic pushdown automata
• Strict deterministic grammars
• On the Parsing of Deterministic Languages
• Some remarks on the KH algorithm fors-grammars
• The equivalence problem for deterministic finite-turn pushdown automata
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Deterministic context free languages
• On the equivalence and containment problems for context-free languages
• Properties of deterministic top-down grammars
• Real-Time Strict Deterministic Languages

This page was built for publication: On equivalence of grammars through transformation trees