Characterizations of recursively enumerable languages by means of insertion grammars
From MaRDI portal
Publication:1275078
DOI10.1016/S0304-3975(97)00079-0zbMath0913.68126MaRDI QIDQ1275078
Arto Salomaa, Gheorghe Păun, Carlos Martín-Vide
Publication date: 12 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00079-0
68Q42: Grammars and rewriting systems
Related Items
Unnamed Item, Morphic characterizations of languages in Chomsky hierarchy with insertion and locality, Theoretical and computational properties of transpositions, Computational power of insertion-deletion (P) systems with rules of size two, P systems with minimal insertion and deletion, On the weight of universal insertion grammars, Context-free insertion-deletion systems, Hybrid networks of evolutionary processors are computationally complete, On the computing powers of \(\mathcal{L}\)-reductions of insertion languages, Derivation languages and descriptional complexity measures of restricted flat splicing systems, Regulated RNA rewriting: Modelling RNA editing with guided insertion, Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion, Circular Post Machines and P Systems with Exo-insertion and Deletion, MORPHIC CHARACTERIZATIONS OF LANGUAGE FAMILIES IN TERMS OF INSERTION SYSTEMS AND STAR LANGUAGES, REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS, Further Results on Insertion-Deletion Systems with One-Sided Contexts, New Morphic Characterizations of Languages in Chomsky Hierarchy Using Insertion and Locality
Cites Work