String Assembling Systems

Martin Kutrib; Matthias Wendlandt

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2012)

  • Volume: 46, Issue: 4, page 593-613
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Kutrib, Martin, and Wendlandt, Matthias. "String Assembling Systems." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 46.4 (2012): 593-613. <http://eudml.org/doc/272991>.

@article{Kutrib2012,
abstract = {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.},
author = {Kutrib, Martin, Wendlandt, Matthias},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {string assembling; double-stranded sequences; stateless; two-head finite automata; decidability; closure properties; string assembling systems; double-stranded sequence of symbols; piecewise assembly; nondeterministic one-way two-head finite automata},
language = {eng},
number = {4},
pages = {593-613},
publisher = {EDP-Sciences},
title = {String Assembling Systems},
url = {http://eudml.org/doc/272991},
volume = {46},
year = {2012},
}

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
PB - EDP-Sciences
VL - 46
IS - 4
SP - 593
EP - 613
AB - 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.
LA - eng
KW - string assembling; double-stranded sequences; stateless; two-head finite automata; decidability; closure properties; string assembling systems; double-stranded sequence of symbols; piecewise assembly; nondeterministic one-way two-head finite automata
UR - http://eudml.org/doc/272991
ER -

References

top
  1. [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. [2] J. Hartmanis, On non-determinancy in simple computing devices. Acta Inf.1 (1972) 336–344. Zbl0229.68014MR317582
  3. [3] M. Holzer, M. Kutrib and A. Malcher, Multi-head finite automata : origins and directions. Theoret. Comput. Sci.412 (2011) 83–96. Zbl1207.68188MR2779447
  4. [4] O.H. Ibarra, A note on semilinear sets and bounded-reversal multihead pushdown automata. Inf. Process. Lett.3 (1974) 25–28. Zbl0294.68019MR347142
  5. [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. Zbl1184.68316MR2590137
  6. [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. Zbl0904.68127MR1623221
  7. [7] R. McNaughton, Algebraic decision procedures for local testability. Math. Syst. Theory8 (1974) 60–76. Zbl0287.02022MR392544
  8. [8] W.F. Ogden, A helpful result for proving inherent ambiguity. Math. Syst. Theory2 (1968) 191–194. Zbl0175.27802MR233645
  9. [9] C.H. Papadimitriou, Computational Complexity. Addison-Wesley (1994) Zbl0833.68049MR1251285
  10. [10] G. Păun and G. Rozenberg, Sticker systems. Theoret. Comput. Sci.204 (1998) 183–203. Zbl0908.68058MR1637532
  11. [11] E.L. Post, A variant of a recursively unsolvable problem. Bull. AMS52 (1946) 264–268. Zbl0063.06329MR15343
  12. [12] A. Salomaa, Formal Languages. Academic Press, New York (1973) Zbl0686.68003MR438755
  13. [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. Zbl1175.68180MR2454747
  14. [14] A.C. Yao and R.L. Rivest, k + 1 heads are better than k. J. ACM 25 (1978) 337–340. Zbl0372.68017MR483728
  15. [15] Y. Zalcstein, Locally testable languages. J. Comput. Syst. Sci.6 (1972) 151–167. Zbl0242.68038MR307538

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.