Header menu link for other important links
X
Binding-blocking automata
Kamala Krithivasan
Published in
2013
Volume: 90
   
Issue: 9
Pages: 1809 - 1831
Abstract
We propose an automaton model called as binding-blocking automaton (BBA). It is a finite state automaton together with the ability to block some symbols and postpone them for reading by the head at a later time. The idea of blocking some symbols from being read by the head and unblocking when the system requires to read is motivated by peptide computing where some parts of peptide sequences are blocked by attaching an antibody with higher affinity and unblocked at a later point by the removal of the appropriate antibody. We study the variants of such systems, analyse the power of each variants and show various hierarchy results involving them. We also define normal-forms of binding-blocking automata for one of its variants and also show that the acceptance power of this variant of BBA is strictly less than that of multi-head finite automata. © 2013 Copyright Taylor and Francis Group, LLC.
About the journal
JournalInternational Journal of Computer Mathematics
ISSN00207160
Open AccessNo
Concepts (9)
  •  related image
    AUTOMATA
  •  related image
    AUTOMATON MODEL
  •  related image
    MOLECULAR COMPUTING
  •  related image
    MULTI-HEAD AUTOMATA
  •  related image
    PEPTIDE SEQUENCES
  •  related image
    Antibodies
  •  related image
    Finite automata
  •  related image
    Formal languages
  •  related image
    Peptides