Insertion languages
References (24)
- et al.
The algebraic theory of context-free languages
Full AFL's and nested iterated substitution
Inform. and Control
(1970)A characterization of the context-free languages
J. Comput. System Sci.
(1971)The power of synchronizing operations on strings
Theoret. Comput. Sci.
(1981)On the enlargement of the class of regular languages by the shuffle closure
Inform. Process. Lett.
(1983)Infinite regular Thue systems
Theoret. Comput. Sci. (Fund. Stud.)
(1983)Some definitional suggestions for automata theory
J. Comput. System Sci.
(1967)Confluent and other types of Thue systems
J. Assoc. Comput. Mach.
(1982)- et al.
Some properties of conversion
Trans. Amer. Math. Soc.
(1939) Church-Rosser congruences on free semigroups
Une generalization des ensembles de Dyck
Israel J. Math.
(1971)
Cited by (45)
On the computing powers of L-reductions of insertion languages
2021, Theoretical Computer ScienceUniversal insertion grammars of size two
2020, Theoretical Computer ScienceCitation Excerpt :There are several related models using a similar principle of insertion or deletion of a string in a specified context. We cite guided-insertion systems [3] used to model RNA editing, leftist grammars [20] used to model accessibility problems in protection systems, restarting automata [10] used to model the analysis by reduction and the insertion operation from [8] introduced as a generalization of the concatenation (and which corresponds to a context-free insertion grammar). Since an insertion grammar is a pure grammar, an additional squeezing mechanism must be used in order to obtain a final language, as otherwise the described language class will have poor closure properties.
Outfix-guided insertion
2017, Theoretical Computer ScienceOn the computational completeness of graph-controlled insertion–deletion systems with binary sizes
2017, Theoretical Computer ScienceUnavoidable sets and circular splicing languages
2017, Theoretical Computer ScienceINSERTION-DELETION WITH SUBSTITUTIONS II: ABOUT THE ROLE OF ONE-SIDED CONTEXT
2023, Journal of Automata, Languages and Combinatorics
Copyright © 1983 Published by Elsevier Inc.