Nonterminal Controlled String Assembling Systems
Henning Bordihn, Martin Kutrib, Matthias Wendlandt · Universitätsbibliothek Gießen · 2014
String assembling systems are biologically inspired mechanisms that generate strings by assembling substrings to the upper and the lower strand of double-stranded strings. We consider the variant where, at both ends, auxiliary (nonterminal) symbols may appear as encodings of ordinary (terminal) symbols, controlling the string assembling process. Those bidirectional systems are compared with unidirectional ones, where substrings can only be assembled at the right end. We show that, in contrast to string assembling systems without auxiliary symbols, bi- and unidirectional nonterminal controlled string assembling systems are equally powerful and characterize the family of languages accepted by nondeterministic one-way two-head finite automata. Some further results are derived comparing nonterminal controlled string assembling systems with traditional complexity and formal language classes.