Insertion languages

doi:10.1016/0020-0255(83)90023-3

Information Sciences

Volume 31, Issue 1, October 1983, Pages 77-89

https://doi.org/10.1016/0020-0255(83)90023-3 Get rights and content

Abstract

The operations of insertion ( ← ) and iterated insertion ( ←_∗ ) are simple variants of Kleene's operations · and ∗ [15] in a manner similar to the operations shuffle and iterated shuffle (see e.g. [13, 23, 20, 14]). Using the operation of iterated insertion, we can generate both the semi-Dyck and the two-sided Dyck languages from certain finite subsets of these languages. Thus the class of languages of the form $S^{←}^{∗}$ for finite S forms a natural class of generalized Dyck languages. This class is equivalent to the class of pure unitary languages discussed in [6]. We investigate this class further, by examining for it the problems of equivalence, ambiguity, and determinism, all of which are easily decidable. On the other hand, we show that the problem “ $S^{←} ∗ ∩ T^{←} ∗ = {λ}?$ ” is undecidable for finite, unambiguous S and T. Furthermore, by extending the regular expressions to include the operations ← and $←_{∗}$ , we obtain the class of insertion languages which generalizes both the regular languages and the Dyck languages, but is properly contained within the class of context-free languages. Our main result here is that the problem “ $L = ∑^{∗} ?$ ” is undecidable for the class of insertion languages. From this result, it follows that the equivalence problem and the problem “IsL regular?” are also undecidable for this class.

References (24)

N. Chomsky et al.
The algebraic theory of context-free languages
S. Greibach
Full AFL's and nested iterated substitution
Inform. and Control
(1970)
J. Gruska
A characterization of the context-free languages
J. Comput. System Sci.
(1971)
M. Jantzen
The power of synchronizing operations on strings
Theoret. Comput. Sci.
(1981)
J. Jedrzejowicz
On the enlargement of the class of regular languages by the shuffle closure
Inform. Process. Lett.
(1983)
C. O'Dunlaing
Infinite regular Thue systems
Theoret. Comput. Sci. (Fund. Stud.)
(1983)
D. Scott
Some definitional suggestions for automata theory
J. Comput. System Sci.
(1967)
R.V. Book
Confluent and other types of Thue systems
J. Assoc. Comput. Mach.
(1982)
A. Church et al.
Some properties of conversion
Trans. Amer. Math. Soc.
(1939)
Y. Cochet
Church-Rosser congruences on free semigroups

Y. Cochet et al.

Une generalization des ensembles de Dyck

Israel J. Math.

(1971)

A. Ehrenfeucht, D. Haussler, and G. Rozenberg, On regularity of context-free languages, Theoret. Comput. Sci., to...

Cited by (45)

On the computing powers of L-reductions of insertion languages
2021, Theoretical Computer Science
We investigate the computing power of the following language operation %: Given two languages $L_{1}$ over Σ and $L_{2}$ over Γ with $Γ \subset Σ$ , we consider the language operation $L_{1} % L_{2} = {u_{0} u_{1} \dots u_{n} | \exists u = u_{0} v_{1} u_{1} \dots v_{n} u_{n} \in L_{1} and \exists v_{i} \in L_{2} (1 \leq \forall i \leq n)}$ . In this case we say that $L (= L_{1} % L_{2})$ is the $L_{2}$ -reduction of $L_{1}$ . This is extended to the language families as follows: $L_{1} % L_{2} = {L_{1} % L_{2} | L_{1} \in L_{1}, L_{2} \in L_{2}}$ . Among many works concerning Dyck-reductions, for the family of recursively enumerable languages $RE$ , it was shown that $LIN % {EQ} = RE$ (Jantzen & Petersen, 1994) with $EQ = {x^{n} {\overline{x}}^{n} | n \in N}$ and that min- $LIN % {D_{2}} = RE$ (Hirose & Okawa, 1996, and Latteux & Turakainen, 1990), where $LIN$ and min- $LIN$ are the families of linear and minimal linear context-free languages, respectively.
In this paper, we show that each recursively enumerable language L can be represented in the form $L = K % D$ , for some $K \in {INS}_{3}^{0}$ and a Dyck language D, where ${INS}_{⁎}^{0}$ ( ${INS}_{3}^{0}$ ) denotes the family of insertion languages (insertion languages where the maximum length of the string to be inserted is 3). We can refine it as ${INS}_{⁎}^{0} % {D_{2}} = RE$ , where $D_{2}$ denotes the Dyck language over binary alphabet. For context-free languages, we show that ${INS}_{3}^{0} % F = CF$ , where $F$ is the family of finite sets. This also derives that ${INS}_{⁎}^{0} % {MIR} = CF$ with $MIR = {x {\overline{x}}^{R} | x \in {0, 1}^{⁎}}$ . Further, for regular languages, it is shown that each regular language R can be represented in the form $R = K % F$ , for some $K \in {INS}_{2}^{0}$ and a finite set $F = {a b \overline{b} \overline{a} | a \in V}$ . We also present some results which characterize the computability and properties of $L$ in the framework of $L_{2}$ -reduction of $L_{1}$ .
It is intriguing to note that, from the DNA computing point of view, the notion of L-reduction is naturally motivated by a molecular biological functioning well-known as DNA(RNA) splicing occurring in most eukaryotic genes.
Universal insertion grammars of size two
2020, Theoretical Computer Science
Citation 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.
In this paper, we show that pure insertion grammars of size 2 (i.e., inserting two symbols in a left and right context, each consisting of two symbols) can characterize all recursively enumerable languages. This is achieved by either applying an inverse morphism and a weak coding, or a left (right) quotient with a regular $L O C (2)$ language, or an intersection with a $L O C (2)$ language and a weak coding. The obtained results improve the descriptional complexity of insertion grammars and complete the picture of known results on insertion-deletion systems that are motivated from the DNA computing area.
Outfix-guided insertion
2017, Theoretical Computer Science
Motivated by work on bio-operations on DNA strings, we consider an outfix-guided insertion operation that can be viewed as a generalization of the overlap assembly operation on strings studied previously. As the main result we construct a finite language L such that the outfix-guided insertion closure of L is non-regular. We consider also the closure properties of regular and (deterministic) context-free languages under the outfix-guided insertion operation and decision problems related to outfix-guided insertion. Deciding whether a language recognized by a deterministic finite automaton is closed under outfix-guided insertion can be done in polynomial time. The complexity of the corresponding question for nondeterministic finite automata remains open.
On the computational completeness of graph-controlled insertion–deletion systems with binary sizes
2017, Theoretical Computer Science
A graph-controlled insertion–deletion (GCID) system is a regulated extension of an insertion–deletion system. Such a system has several components and each component has some insertion–deletion rules. The transition is performed by any applicable rule in the current component on a string and the resultant string is then moved to the target component specified in the rule. The language of the system is the set of all terminal strings collected in the final component. The parameters in the size $(k; n, i^{'}, i^{″}; m, j^{'}, j^{″})$ of a GCID system denote (from left to right) the maximum number of components, the maximal length of the insertion string, the maximal length of the left context for insertion, the maximal length of the right context for insertion; the last three parameters follow a similar representation with respect to deletion.
In this paper, we discuss the computational completeness of the families of GCID systems of size $(k; 1, i^{'}, i^{″}; 1, j^{'}, j^{″})$ with $k \in {3, 5}$ and for (nearly) all values of $i^{'}, i^{″} j^{'}, j^{″} \in {0, 1}$ . All proofs are based on the simulation of type-0 grammars given in Special Geffert Normal Form (SGNF). The novelty in our proof presentation is that the context-free and the non-context-free rules of the given SGNF grammar are simulated by GCID systems of different sizes and finally we combine them by stitching and overlaying to characterize the recursive enumerable languages. This proof presentation greatly simplifies and unifies the proof of such characterization results. We also connect some of the obtained GCID simulations to the domain of insertion–deletion P systems.
Unavoidable sets and circular splicing languages
2017, Theoretical Computer Science
Circular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A, an initial set I of circular words, and a set R of rules. In this paper, we focus on the still unknown relations between regular languages and circular splicing systems with a finite initial set and a finite set R of rules represented by a pair of letters ( $(1, 3)$ -CSSH systems). When $R = A \times A$ , it is known that the set of all words corresponding to the splicing language belongs to the class of pure unitary languages, introduced by Ehrenfeucht, Haussler, Rozenberg in 1983. They also provided a characterization of the regular pure unitary languages, based on the notions of unavoidable sets and well quasi-orders. We partially extend these notions and their results in the more general framework of the $(1, 3)$ -CSSH systems.
INSERTION-DELETION WITH SUBSTITUTIONS II: ABOUT THE ROLE OF ONE-SIDED CONTEXT
2023, Journal of Automata, Languages and Combinatorics

View all citing articles on Scopus

View full text

Insertion languages

Abstract

Inform. and Control

J. Comput. System Sci.

Theoret. Comput. Sci.

Inform. Process. Lett.

Theoret. Comput. Sci. (Fund. Stud.)

J. Comput. System Sci.

Confluent and other types of Thue systems

J. Assoc. Comput. Mach.

Some properties of conversion

Trans. Amer. Math. Soc.

Church-Rosser congruences on free semigroups

Une generalization des ensembles de Dyck

Israel J. Math.