Voir la notice de l'article provenant de la source Numdam
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.
@article{ITA_2012__46_4_593_0,
author = {Kutrib, Martin and Wendlandt, Matthias},
title = {String {Assembling} {Systems}},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {593--613},
publisher = {EDP-Sciences},
volume = {46},
number = {4},
year = {2012},
doi = {10.1051/ita/2012020},
mrnumber = {3107865},
zbl = {1279.68080},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2012020/}
}
TY - JOUR AU - Kutrib, Martin AU - Wendlandt, Matthias TI - String Assembling Systems JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2012 SP - 593 EP - 613 VL - 46 IS - 4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2012020/ DO - 10.1051/ita/2012020 LA - en ID - ITA_2012__46_4_593_0 ER -
%0 Journal Article %A Kutrib, Martin %A Wendlandt, Matthias %T String Assembling Systems %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2012 %P 593-613 %V 46 %N 4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2012020/ %R 10.1051/ita/2012020 %G en %F ITA_2012__46_4_593_0
Kutrib, Martin; Wendlandt, Matthias. String Assembling Systems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 4, pp. 593-613. doi: 10.1051/ita/2012020
Cité par Sources :