On the computing powers of L-reductions of insertion languages

DOI10.1016/J.TCS.2020.11.029MaRDI QIDQ1998879zbMATH OpenOpenAlexFDO

Authors Fumiya Okubo, Takashi Yokomori

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 languagesDyck-reductioninsertion languagesinsertion systemsrecursively enumerable languages

Mathematics Subject Classification ID

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

Recommendations

• REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS
• scientific article; zbMATH DE number 1342113
• Insertion-deletion systems with substitutions. I
• Insertion languages
• On the weight of universal insertion grammars

Cites work

• A homomorphic characterization of recursively enumerable languages
• A variant of random context grammars: Semi-conditional grammars
• Cancellation in context-free languages: enrichment by reduction
• Characterizations of recursively enumerable languages by means of insertion grammars
• Context-Free Grammars and XML Languages
• Context-free insertion-deletion systems
• Contextual insertions/deletions and computability
• Finiteness Conditions on Subgroups and Formal Language Theory
• How to Make Arbitrary Grammars Look Like Context-Free Grammars
• scientific article; zbMATH DE number 4139308 (Why is no real title available?)
• scientific article; zbMATH DE number 4024816 (Why is no real title available?)
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 559222 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• scientific article; zbMATH DE number 3307580 (Why is no real title available?)
• Insertion languages
• Monadic Thue systems
• Morphic characterizations of language families based on local and star languages
• Morphic characterizations of language families in terms of insertion systems and star languages
• Morphic characterizations of languages in Chomsky hierarchy with insertion and locality
• Normal forms for phrase-structure grammars
• On characterizations of recursively enumerable languages
• On minimal context-free insertion-deletion systems
• On the computational power of insertion-deletion systems
• On the weight of universal insertion grammars
• Pure grammars
• REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS
• Representing recursively enumerable languages by iterated deletion
• Shuffle and scattered deletion closure of languages
• Some remarks on derivations in general rewriting systems
• The computational capability of chemical reaction automata
• Universal insertion grammars of size two

Cited in

(3)

• Corrigendum to: ``On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
• \(\mathcal{L}\)-reduction computation revisited
• Aspects of Molecular Computing

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1998879)