Conditional Concatenation

Article type: Research Article

Authors: Dassow, Jürgen | Martín-Vide, Carlos | Păun, Gheorghe | Rodríguez-Patón, Alfonso

Abstract: Inspired from biochemistry and DNA computing, we introduce several variants of controlled concatenation of strings and languages: a finite set of pairs of strings is given and two arbitrary strings are concatenated only when among their substrings (scattered substrings, of various forms) we can find a pair in this control set. Five types of non-iterated and iterated (like Kleene closure) conditional concatenations are considered. The closure properties of abstract families of languages (hence also of families in the Chomsky hierarchy) are settled. They are similar to the closure properties under usual concatenation and Kleene closure. A representation of regular languages in terms of these operations (and a coding) is also given. Then, we use the new concatenation operations as basic operations in Chomsky grammars: rewriting a nonterminal means concatenating a new string with the strings to the left and the right of that nonterminal, hence restricted concatenations can be used. Context-free grammars working in this restricted manner can generate non-context-free languages; in one case, characterizations of recursively enumerable or of context-sensitive languages are obtained, depending on using or not erasing rules. Some topics for further research are also suggested.

Keywords: closure under controlled concatenation, characterization of regular languages

Journal: Fundamenta Informaticae, vol. 44, no. 4, pp. 353-372, 2000