On Restricted Bio-Turing Machines

• Autorzy: Raghavan R. , Ramesh H. , Gheorghe M. , Krishna S.N.
• Języki publikacji: EN

Abstrakty

EN

Here we continue the study of bio-Turing machines introduced in [2] and further investigated in [17]. We introduce a restricted model of bio-Turingmachine and we investigate its computational power, a hierarchy of languages accepted, and deterministic and nondeterministic variants. A comprehensive example illustrating the modelling power of the introduced machine ends the paper.

Słowa kluczowe

EN

Bio-Turing machines; restricted bio-Turing machine

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 309--320
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Raghavan R.

autor

Ramesh H.

autor

Gheorghe M.

autor

Krishna S.N.

• Department of Mathematics, Indian Institute of Technology Chennai, Chennai, India,

Bibliografia

• [1] J. Aguado, T Bǎlǎnescu, A.J. Cowling, M. Gheorghe, M. Holcombe, F. Ipate, P systems with replicated rewriting and stream X-machines, Fundamenta Informaticae, 49 (1-3), 2002, 17 - 33.
• [2] F. Bernardini, M. Gheorghe, N. Krasnogar, Gh. Pǎun, Turing machines with cells on the tape, Proc. of the ESF Exploratory Workshop on Cellular Computing (Complexity Aspects), Sevilla (Spain), 2005, 63 - 74.
• [3] F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan, How to synchronize the activity of all components of a P system?, International Journal of Foundations of Computer Science, 19 (5), 2008, 1183 -1198.
• [4] G. Ciobanu, Distributed algorithms over communicating membrane systems, BioSystems, 70 (2), 2003, 123 - 133.
• [5] Z. Dang, O.H. Ibarra, S. Woodworth, H.C. Yen, On symport/antiport systems and semilinear sets, Preproceedings of WMC6, Vienna (Austria), 2005, 312 - 335.
• [6] M.J. Dinneen, Y.-B. Kim, R. Nicolescu, P systems and Byzantine agreement, Journal of Logic and Algebraic Programming, 79 (6), 2010, 334 - 349.
• [7] G.J. Holzmann, The model checker SPIN, IEEE Transactions on Software Engineering, 23 (5), 1997, 279 - 295.
• [8] O.H. Ibarra, On determinism versus nondeterminismin P systems, Theoretical Computer Science, 344 (2-3), 2005, 120 - 133.
• [9] O.H. Ibarra, On membrane hierarchy in P systems, Theoretical Computer Science, 334 (1-3), 2005, 115 - 129.
• [10] O.H. Ibarra, S. Woodworth, On bounded symport/antiport P systems, Proc. DNA11, London, Ontario, Canada, 2005, 37 - 48.
• [11] F. Ipate, R. Lefticaru, C. Tudose, Formal verification of P systems using SPIN, International Journal of Foundations of Computer Science, 22 (1), 2011, 133 - 142.
• [12] M.L. Minsky, Computation: finite and infinite machines. Prentice Hall, Englewood Cliffs, New Jersey, USA 1967.
• [13] B. Monien, Two-way multihead automata over one-letter alphabet, RAIRO Informatique Theorique, 14 (1), 1980, 67 - 82.
• [14] A. Pǎun, Gh. Pǎun, The power of communication: P systems with symport/antiport, New Generation Computers, 20, 3 (2002), 295 - 306.
• [15] Gh. Pǎun, Membrane computing: an introduction, Springer-Verlag, Berlin, 2002.
• [16] Gh. Pǎun, G. Rozenberg, A. Salomaa (Eds.), The Oxford handbook of membrane computing, Oxford University Press, 2009.
• [17] H. Ramesh, S.N. Krishna, R. Rama, On the power of bio-Turing machines, Proc. UC2006, York (UK), LNCS 4135, Springer, Berlin, 2006, 243 - 253.
• [18] W. Savitch, Relationships between nondeterministic and deterministic tape complexities, Acta Informatica, 2, 1973, 249 - 252.