Control Languages Associated with Spiking Neural P Systems

We consider labeled spiking neural P systems, which are usual spiking neural P systems with a label associated with every rule; the labels are symbols of a given alphabet or can be lambda (empty). The rules used in a transition should have either the empty label or the same label from the chosen alphabet. In this way, a string is associated with each halting computation, called the control word of the computation. The set of all control words associated with computations in a given spiking neural P system form the control language of the system. We study the family of control languages of spiking neural P systems in comparison with the families of finite, regular, context-free, context-sensitive, and recursively enumerable languages. In the restricted case when in each step at least one rule with a non-empty label is used, every regular language is a control language, there are context-sensitive non-context-free languages of this type, but not all context-free languages are control languages of a spiking neural P system. All languages that are accepted by labeled spiking neural P systems are context-sensitive. If transitions with all rules labeled with lambda are allowed, then each recursively enumerable language can be the control word of a spiking neural P system.