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

DOI10.1016/0304-3975(84)90045-8MaRDI QIDQ1069311zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Recommendations

• On the equivalence problem of context-free and DT0L languages
• Publication:4284264
• 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

Cites work

• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Context-free grammar forms
• Denseness, maximality, and decidability of grammatical families
• Finitary and infinitary interpretations of languages
• Grammar and L forms: an introduction
• Sub-regular grammar forms

Cited in

(3)

• scientific article; zbMATH DE number 4033715 (Why is no real title available?)
• Density of grammar forms. part I
• Density of grammar forms part II

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)