Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-25T16:21:51.104Z Has data issue: false hasContentIssue false
  • English
  • Français

String Assembling Systems

Published online by Cambridge University Press:  02 August 2012

Martin Kutrib  and
Matthias Wendlandt
Martin Kutrib
Affiliation:
Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. [email protected], [email protected]
Matthias Wendlandt
Affiliation:
Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. [email protected], [email protected]
Get access

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.

Keywords

String assemblingdouble-stranded sequencesstatelesstwo-head finite automatadecidabilityclosure properties
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 46 , Issue 4: Special Issue: Non-Classical Models ofAutomata and Applications III (NCMA-2011) , October 2012 , pp. 593 - 613
Copyright
© EDP Sciences 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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.
Hartmanis, J., On non-determinancy in simple computing devices. Acta Inf. 1 (1972) 336–344. Google Scholar
Holzer, M., Kutrib, M. and Malcher, A., Multi-head finite automata : origins and directions. Theoret. Comput. Sci. 412 (2011) 83–96. Google Scholar
Ibarra, O.H., A note on semilinear sets and bounded-reversal multihead pushdown automata. Inf. Process. Lett. 3 (1974) 25–28. Google Scholar
Ibarra, O.H., Karhumäki, J. and Okhotin, A., On stateless multihead automata : hierarchies and the emptiness problem. Theoret. Comput. Sci. 411 (2009) 581–593. Google Scholar
Kari, L., Păun, G., Rozenberg, G., Salomaa, A. and Yu, S., DNA computing, sticker systems, and universality. Acta Inf. 35 (1998) 401–420. Google Scholar
McNaughton, R., Algebraic decision procedures for local testability. Math. Syst. Theory 8 (1974) 60–76. Google Scholar
Ogden, W.F., A helpful result for proving inherent ambiguity. Math. Syst. Theory 2 (1968) 191–194. Google Scholar
C.H. Papadimitriou, Computational Complexity. Addison-Wesley (1994)
Păun, G. and Rozenberg, G., Sticker systems. Theoret. Comput. Sci. 204 (1998) 183–203. Google Scholar
Post, E.L., A variant of a recursively unsolvable problem. Bull. AMS 52 (1946) 264–268. Google Scholar
A. Salomaa, Formal Languages. Academic Press, New York (1973)
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.
Yao, A.C. and Rivest, R.L., k + 1 heads are better than k. J. ACM 25 (1978) 337–340. Google Scholar
Zalcstein, Y., Locally testable languages. J. Comput. Syst. Sci. 6 (1972) 151–167. Google Scholar