On the computing powers of \(\mathcal{L}\)-reductions of insertion languages

DOI10.1016/j.tcs.2020.11.029zbMath1502.68165OpenAlexW3108379800MaRDI QIDQ1998879

Publication date: 9 March 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.11.029

zbMATH Keywords

context-free languages recursively enumerable languages insertion languages Dyck-reduction insertion systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Related Items (1)

\(\mathcal{L}\)-reduction computation revisited

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Morphic characterizations of languages in Chomsky hierarchy with insertion and locality
Contextual insertions/deletions and computability
Insertion languages
On the weight of universal insertion grammars
A homomorphic characterization of recursively enumerable languages
A variant of random context grammars: Semi-conditional grammars
Monadic Thue systems
On characterizations of recursively enumerable languages
Characterizations of recursively enumerable languages by means of insertion grammars
Cancellation in context-free languages: enrichment by reduction
On the computational power of insertion-deletion systems
Shuffle and scattered deletion closure of languages
Context-free insertion-deletion systems
Representing recursively enumerable languages by iterated deletion
Universal insertion grammars of size two
The computational capability of chemical reaction automata
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
Context-Free Grammars and XML Languages
Finiteness Conditions on Subgroups and Formal Language Theory
Pure grammars
Normal forms for phrase-structure grammars
How to Make Arbitrary Grammars Look Like Context-Free Grammars
Morphic Characterizations of Language Families Based on Local and Star Languages
Some remarks on derivations in general rewriting systems

This page was built for publication: On the computing powers of \(\mathcal{L}\)-reductions of insertion languages