On equivalence of grammars through transformation trees
From MaRDI portal
Publication:1259173
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
EquivalenceGrammar Oriented Decision ProcedureProblem for Deterministic Context-Free LanguagesStrict Deterministic GrammarsTransformation Trees
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On equivalence of grammars through transformation trees
