RAIRO-Theor. Inf. Appl.
Volume 46, Number 4, October-December 2012Special Issue: Non-Classical Models of Automata and Applications III (NCMA-2011)
|Page(s)||593 - 613|
|Published online||02 August 2012|
String Assembling Systems
Received: 8 November 2011
Accepted: 13 June 2012
We introduce and investigate string assembling systems which form a computational model that generates strings from copies out of a finite set of assembly units. The underlying mechanism is based on piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. The generation is additionally controlled by the requirement that the first symbol of a unit has to be the same as the last symbol of the strand generated so far, as well as by the distinction of assembly units that may appear at the beginning, during, and at the end of the assembling process. We start to explore the generative capacity of string assembling systems. In particular, we prove that any such system can be simulated by some nondeterministic one-way two-head finite automaton, while the stateless version of the two-head finite automaton marks to some extent a lower bound for the generative capacity. Moreover, we obtain several incomparability and undecidability results as well as (non-)closure properties, and present questions for further investigations.
Mathematics Subject Classification: 68Q05 / 68Q42
Key words: String assembling / double-stranded sequences / stateless / two-head finite automata / decidability / closure properties
© EDP Sciences 2012
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.