Binding-blocking automata

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.

Keywords:

• automata
• formal languages
• peptide computing
• molecular computing
• multi-head automata

2010 AMS Subject Classifications :

• 68Q45
• 68Q05

Notes

The state from where no transition is possible.

Heads cannot sense if two or more heads are reading the same tape cell or not.