神经膜计算系统在穷举使用规则下产生的字符串语言.pdfVIP

1 On String Languages Generated by Spiking Neural P Systems with Exhaustive Use of Rules Xingyi Zhang Xiangxiang Zeng Linqiang Pan∗ Key Laboratory of Image Processing and Intelligent Control Department of Control Science and Engineering Huazhong University of Science and Technology, Wuhan 430074, Hubei, China Abstract We continue the study of spiking neural P systems with exhaustive use of rules by considering these computing devices as language generators, where a step is associated with a symbol according to the number of spikes emitted by the output neuron and the sequence of these symbols associated with a halting computation of a given system constitutes a string. About string languages generated by spiking neural P systems with exhaustive use of rules, two cases are considered, one is interpreting a step as a new symbol when no spike is emitted, the other is interpreting it as the empty string. In all these cases, it is proved that finite and recursively enumerable languages are characterized by spiking neural P systems in exhaustive mode. Moreover, the relationships with regular languages are also investigated. Keywords: Membrane computing; Register machine; SN P systems 1 Introduction The spiking neural P systems (in short, SN P systems) are a class of computing devices introduced in [3], which is an attempt to incorporate the idea of spiking neurons into the area of membrane computing. Although the research of SN P systems was initiated recently, in the year of 2006, it became a hot research are