Header menu link for other important links
X
On the power of bio-turing machines
H. Ramesh,
Published in Springer Verlag
2006
Volume: 4135 LNCS
   
Pages: 243 - 253
Abstract
In this paper, we continue the study of Bio-Turing machines introduced in [1]. It was proved in [1] that using two differentiated cells, and using antiport rules of weight 2, one can recognize the family 1RE. We show here that with just one differentiated cell, 1RE can be characterized, by using antiport rules of weight 2, or by using symport rules of weight 3. We also prove that RE can be characterized using arbitrary alphabets, using 2 differentiated cells, and antiport rules of weight 2. Finally, we examine the computational power when there are no differentiated cells and show that non-regular languages can be accepted. © Springer-Verlag Berlin Heidelberg 2006.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
ISSN03029743
Open AccessNo
Concepts (6)
  •  related image
    Computational methods
  •  related image
    Formal languages
  •  related image
    Arbitrary alphabets
  •  related image
    Bio-turing machines
  •  related image
    Computational power
  •  related image
    Turing machines