Some decidability problems of sentential formst †

DOI10.1080/00207167908803161zbMath0405.68061OpenAlexW2110180792MaRDI QIDQ4191619

Martti Penttonen, Tero J.Harju

Publication date: 1979

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207167908803161

zbMATH Keywords

DecidabilityAmbiguityEquivalenceContext-Free GrammarsRegular SetsChomsky GrammarsContext-Sensitive Sf-LanguagesPhrase-Structure GrammarSentential Forms

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25)

Related Items (9)

On form-equivalence of deterministic pure grammar forms ⋮ Unnamed Item ⋮ Decidability Questions for Insertion Systems and Related Models ⋮ A remark on regularity of parallel languages ⋮ Representation theorems using DOS languages ⋮ Two-symbol DOS systems generating regular languages ⋮ It is decidable whether a regular language is pure context-free ⋮ On DOS languages and DOS mappings ⋮ A regularity test for dual bordered OS systems

Cites Work

• The unsolvability of the equality problem for sentential forms of context-free grammars
• Direct proofs of the undecidability of the equivalence problem for sentential forms of linear context-free grammars and the equivalence problem for OL systems
• On sentential forms of context-free grammars

This page was built for publication: Some decidability problems of sentential formst †