Author name cluster

Gabriel Thierrin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2000 Journal Article

Shuffle and scattered deletion closure of languages

Masami Ito
Lila Kari
Gabriel Thierrin

We introduce and study the notion of shuffle residual of a language L: the set containing the words whose shuffle with L is completely included in L. Several properties and a characterization of the shuffle residual of a language are obtained. The shuffle closure of a language L (the smallest language that is shuffle closed and contains L) is investigated. Moreover, conditions for the existence of maximal languages whose shuffle residual equals a given language are obtained. The paper also considers an operation dual to shuffle, namely scattered deletion: the scattered deletion of a word w from u consists of the words obtained by sparsely deleting from u the letters of w, in the order in which they appear in w. The scattered deletion residual and scattered deletion closure of a language are defined and studied. Finally, relationships and interdependencies between shuffle, scattered deletion, and other insertion and deletion operations are obtained.

Details DOI

TCS Journal 1997 Journal Article

Insertion and deletion closure of languages

Masami Ito
Lila Kari
Gabriel Thierrin

To a given language L, we associate the sets ins(L) (resp. del(L)) consisting of words with the following property: their insertion into (deletion from) any word of L yields words which also belong to L. Properties of these sets and of languages which are insertion (deletion) closed are obtained. Of special interest is the case when the language is ins-closed (del-closed) and finitely generated. Then the minimal set of generators turns out to be a maximal prefix and suffix code, which is regular if L is regular. In addition, we study the insertion-base of a language and languages which have the property that both they and their complements are ins-closed.

Details DOI

I&C Journal 1996 Journal Article

Contextual Insertions/Deletions and Computability

Lila Kari
Gabriel Thierrin

We investigate two generalizations of insertion and deletion of words, that have recently become of interest in the context of molecular computing. Given a pair of words (x, y), called a context, the (x, y)-contextual insertion of a wordvinto a worduis performed as follows. For each occurrence ofxyas a subword inu, we include in the result of the contextual insertion the words obtained by insertingvintou, betweenxandy. The (x, y)-contextual deletion operation is defined in a similar way. We study closure properties of the Chomsky families under the defined operations, contextual ins-closed and del-closed languages, and decidability of existence of solutions to equations involving these operations. Moreover, we prove that every Turing machine can be simulated by a system based entirely on contextual insertions and deletions

Details DOI