String Assembling Systems
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 4, pp. 593-613.

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.

DOI : https://doi.org/10.1051/ita/2012020
Classification : 68Q05,  68Q42
Mots clés : string assembling, double-stranded sequences, stateless, two-head finite automata, decidability, closure properties
@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},
zbl = {1279.68080},
mrnumber = {3107865},
language = {en},
url = {http://www.numdam.org/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
DA  - 2012///
SP  - 593
EP  - 613
VL  - 46
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2012020/
UR  - https://zbmath.org/?q=an%3A1279.68080
UR  - https://www.ams.org/mathscinet-getitem?mr=3107865
UR  - https://doi.org/10.1051/ita/2012020
DO  - 10.1051/ita/2012020
LA  - en
ID  - ITA_2012__46_4_593_0
ER  - 
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. http://www.numdam.org/articles/10.1051/ita/2012020/

[1] R. Freund, G. Păun, G. Rozenberg and A. Salomaa, Bidirectional sticker systems, in Pacific Symposium on Biocomputing (PSB). World Scientific, Singapore (1998) 535-546.

[2] J. Hartmanis, On non-determinancy in simple computing devices. Acta Inf. 1 (1972) 336-344. | MR 317582 | Zbl 0229.68014

[3] M. Holzer, M. Kutrib and A. Malcher, Multi-head finite automata : origins and directions. Theoret. Comput. Sci. 412 (2011) 83-96. | MR 2779447 | Zbl 1207.68188

[4] O.H. Ibarra, A note on semilinear sets and bounded-reversal multihead pushdown automata. Inf. Process. Lett. 3 (1974) 25-28. | MR 347142 | Zbl 0294.68019

[5] O.H. Ibarra, J. Karhumäki and A. Okhotin, On stateless multihead automata : hierarchies and the emptiness problem. Theoret. Comput. Sci. 411 (2009) 581-593. | MR 2590137 | Zbl 1184.68316

[6] L. Kari, G. Păun, G. Rozenberg, A. Salomaa and S. Yu, DNA computing, sticker systems, and universality. Acta Inf. 35 (1998) 401-420. | MR 1623221 | Zbl 0904.68127

[7] R. Mcnaughton, Algebraic decision procedures for local testability. Math. Syst. Theory 8 (1974) 60-76. | MR 392544 | Zbl 0287.02022

[8] W.F. Ogden, A helpful result for proving inherent ambiguity. Math. Syst. Theory 2 (1968) 191-194. | MR 233645 | Zbl 0175.27802

[9] C.H. Papadimitriou, Computational Complexity. Addison-Wesley (1994) | MR 1251285 | Zbl 0833.68049

[10] G. Păun and G. Rozenberg, Sticker systems. Theoret. Comput. Sci. 204 (1998) 183-203. | MR 1637532 | Zbl 0908.68058

[11] E.L. Post, A variant of a recursively unsolvable problem. Bull. AMS 52 (1946) 264-268. | MR 15343 | Zbl 0063.06329

[12] A. Salomaa, Formal Languages. Academic Press, New York (1973) | MR 438755 | Zbl 0686.68003

[13] L. Yang, Z. Dang and O.H. Ibarra, On stateless automata and P systems, in Workshop on Automata for Cellular and Molecular Computing. MTA SZTAKI (2007) 144-157. | MR 2454747 | Zbl 1175.68180

[14] A.C. Yao and R.L. Rivest, k + 1 heads are better than k. J. ACM 25 (1978) 337-340. | MR 483728 | Zbl 0372.68017

[15] Y. Zalcstein, Locally testable languages. J. Comput. Syst. Sci. 6 (1972) 151-167. | MR 307538 | Zbl 0242.68038

Cité par Sources :