On sentential forms of context-free grammars

DOI10.1007/BF00571462zbMath0264.68029MaRDI QIDQ2561842

Arto Salomaa

Publication date: 1973

Published in: Acta Informatica (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (23)

On equality of multiplicity sets of regular languages ⋮ Unnamed Item ⋮ Grammars with valuations - a discrete model for self-organization of biopolymers ⋮ On form-equivalence of deterministic pure grammar forms ⋮ On the equivalence problem of context-free and DT0L languages ⋮ The decidability of the DOL-DTOL equivalence problem ⋮ Unnamed Item ⋮ The language equivalence problem for HD0L systems having D0L growths ⋮ An Extension of Complex Role Inclusion Axioms in the Description Logic $\mathcal{SROIQ}$ ⋮ Interactive languages ⋮ Deterministic Lindenmayer languages, nonterminals and homomorphisms ⋮ Classes of formal grammars ⋮ On the decidability of homomorphism equivalence for languages ⋮ The equivalence problem for languages defined by transductions on D0L languages ⋮ Some decidability problems of sentential formst † ⋮ Representation theorems using DOS languages ⋮ Two-symbol DOS systems generating regular languages ⋮ It is decidable whether a regular language is pure context-free ⋮ Solution of a decision problem concerning unary Lindenmayer systems ⋮ On DOS languages and DOS mappings ⋮ Homomorphic images of sentential form languages defined by semi-Thue systems ⋮ A regularity test for dual bordered OS systems ⋮ The equivalence problem of multitape finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• The equivalence problem for deterministic TOL-systems is undecidable
• Pure grammars and pure languages†
• Integral sequential word functions and growth equivalence of lindenmayer systems

This page was built for publication: On sentential forms of context-free grammars