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

DOI10.1016/0304-3975(84)90045-8zbMATH Open0583.68038OpenAlexW2011155708WikidataQ126437697 ScholiaQ126437697MaRDI QIDQ1069311FDOQ1069311

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Grammar and L forms: an introduction
• Context-free grammar forms
• Finitary and infinitary interpretations of languages
• Sub-regular grammar forms
• Denseness, maximality, and decidability of grammatical families

Cited In (3)

• Density of grammar forms. part I
• Title not available (Why is that?)
• Density of grammar forms part II

   Recommendations

• On the equivalence problem of context-free and DT0L languages 👍 👎
• Title not available (Why is that?) 👍 👎
• An undecidable problem for context-free grammars 👍 👎
• On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages 👍 👎
• Decidability of bisimulation equivalence for process generating context-free languages 👍 👎

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1069311)