On the equivalence and containment problems for context-free languages

DOI10.1007/BF01746517zbMath0179.02203OpenAlexW2094274619MaRDI QIDQ5569456

John E. Hopcrofts

Publication date: 1969

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01746517

zbMATH Keywords

languages, automata, networks

Related Items (11)

A theoretical framework for cardinality-based feature models: the semantics and computational aspects ⋮ A subclass of deterministic context-free languages with a decidable inclusion problem ⋮ On the rational subset problem for groups. ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ Observations on the complexity of regular expression problems ⋮ There does not exist an enumerable family of context-free grammars that generates the class of single-valued languages ⋮ On the equivalence, containment, and covering problems for the regular and context-free languages ⋮ On equivalence of grammars through transformation trees ⋮ The Inclusion Problem of Context-Free Languages: Some Tractable Cases ⋮ Theory of formal grammars

Cites Work

• Bounded Algol-Like Languages
• A note on undecidable properties of formal languages

This page was built for publication: On the equivalence and containment problems for context-free languages