The undecidability of form equivalence for context-free and EOL forms

DOI10.1016/0304-3975(84)90045-8zbMath0583.68038OpenAlexW2011155708WikidataQ126437697 ScholiaQ126437697MaRDI QIDQ1069311

Valtteri Niemi

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90045-8

zbMATH Keywords

decidabilityEOL formscontext-free grammar formsequivalence problem between languagesform equivalence problemL formslanguage form

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Density of grammar forms. part I ⋮ Density of grammar forms part II

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Grammar and L forms: an introduction
• Sub-regular grammar forms
• Context-free grammar forms
• Denseness, maximality, and decidability of grammatical families
• Finitary and infinitary interpretations of languages

This page was built for publication: The undecidability of form equivalence for context-free and EOL forms