Pure grammars

DOI10.1016/S0019-9958(80)90131-XzbMath0446.68063MaRDI QIDQ3891788

Hermann Maurer, Arto Salomaa, Derick Wood

Publication date: 1980

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(80)90131-x

zbMATH Keywords

survey; decidability; ambiguity; monogenicity; pure grammars; length sets; language hierarchies

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D60: Computability and recursion theory on ordinals, admissible sets, etc.

Related Items

Decidability Questions for Insertion Systems and Related Models, An Extension of Complex Role Inclusion Axioms in the Description Logic $\mathcal{SROIQ}$, Operations and language generating devices suggested by the genome evolution, Array P systems and pure 2D context-free grammars with independent mode of rewriting, An array P system based on a new variant of pure 2D context-free grammars, Decidability of operation problems for T0L languages and subclasses, A \(P\) system model with pure context-free rules for picture array generation, It is decidable whether a regular language is pure context-free, On DOS languages and DOS mappings, Homomorphic images of sentential form languages defined by semi-Thue systems, Pure 2D picture grammars and languages, A regularity test for dual bordered OS systems, A note on pure grammars, Context-free grammars with selective rewriting, Grammars with valuations - a discrete model for self-organization of biopolymers, On form-equivalence of deterministic pure grammar forms, Characterizations of recursively enumerable languages by means of insertion grammars, Representation theorems using DOS languages, Two-symbol DOS systems generating regular languages, On the computing powers of \(\mathcal{L}\)-reductions of insertion languages, Modular materialisation of Datalog programs, Language generating alphabetic flat splicing P systems, Solutions to four open problems concerning controlled pure grammar systems, Comparison of basic language generating devices (non-deterministic systems), Undecidability of Operation Problems for T0L Languages and Subclasses, A remark on regularity of parallel languages, A note on regular-controlled apical-growth filamentous systems, Pure grammars and pure languages†, Derivation languages of grammar forms†