On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
type: Item
instance of: scholarly article
title: On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
zbMATH Open document ID: 1502.68165
author: Fumiya Okubo
author: Takashi Yokomori
published in: Theoretical Computer Science
publication date: 2021-03-09T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q07
zbMATH DE Number: 7318720
zbMATH Keywords: Dyck-reduction
zbMATH Keywords: recursively enumerable languages
zbMATH Keywords: context-free languages
zbMATH Keywords: insertion systems
zbMATH Keywords: insertion languages
MaRDI profile type: Publication
full work available at URL: j.tcs.2020.11.029
OpenAlex ID: W3108379800
cites work: Context-Free Grammars and XML Languages
cites work: Monadic Thue systems
cites work: Q5526125
cites work: Representing recursively enumerable languages by iterated deletion
cites work: Finiteness Conditions on Subgroups and Formal Language Theory
cites work: Morphic characterizations of languages in Chomsky hierarchy with insertion and locality
cites work: Normal forms for phrase-structure grammars
cites work: Some remarks on derivations in general rewriting systems
cites work: Insertion languages
cites work: A homomorphic characterization of recursively enumerable languages
cites work: Shuffle and scattered deletion closure of languages
cites work: Q3766878
cites work: Cancellation in context-free languages: enrichment by reduction
cites work: Q3471701
cites work: On the weight of universal insertion grammars
cites work: Contextual insertions/deletions and computability
cites work: On characterizations of recursively enumerable languages
cites work: Q5588662
cites work: Context-free insertion-deletion systems
cites work: Characterizations of recursively enumerable languages by means of insertion grammars
cites work: Pure grammars
cites work: MORPHIC CHARACTERIZATIONS OF LANGUAGE FAMILIES IN TERMS OF INSERTION SYSTEMS AND STAR LANGUAGES
cites work: The computational capability of chemical reaction automata
cites work: Morphic Characterizations of Language Families Based on Local and Star Languages
cites work: A variant of random context grammars: Semi-conditional grammars
cites work: Q4289280
cites work: Q4223673
cites work: REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS
cites work: Q4714446
cites work: How to Make Arbitrary Grammars Look Like Context-Free Grammars
cites work: On the computational power of insertion-deletion systems
cites work: Q3517111
cites work: Universal insertion grammars of size two
DOI: 10.1016/J.TCS.2020.11.029
description: scientific article; zbMATH DE number 7318720