Pure grammars

DOI10.1016/S0019-9958(80)90131-XzbMath0446.68063OpenAlexW4212990661MaRDI 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

surveydecidabilityambiguitymonogenicitypure grammarslength setslanguage hierarchies

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (30)

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

This page was built for publication: Pure grammars