最小串行策略下脉冲神经膜系统的语言产生能力  

Language generation ability of SNPS working in min-sequentiality strategy

作　　者：李立[1] 江克勤 Li Li;Jiang Keqin(Anqing Radio and Television University,Anqing 246003,China;School of Computer and Information,Anqing Normal University,Anqing 246133,China)

机构地区：[1]安庆广播电视大学,安徽安庆246003 [2]安庆师范大学计算机与信息学院,安徽安庆246133

出　　处：《南京理工大学学报》2018年第5期597-603,共7页Journal of Nanjing University of Science and Technology

基　　金：国家自然科学基金(61033003);安徽省自然科学基金(1408085MF131);安徽省高校自然科学研究重点项目(KJ2017A942)

摘　　要：为了验证脉冲神经膜系统(SNPS)在运算受限情况下的计算性能,该文在标准SNPS中引入最小串行策略,并研究其语言产生能力。在使用最小串行策略的SNPS的每一步计算中,只有满足相应规则且所含脉冲数最少的神经元才可以激发。首先分析了使用最小串行策略的SNPS与有限语言和正则语言的关系,定义了任意多元字母表到二元字母表的映射,构建了能够产生递归可枚举语言的SNPS,设计了加法模块和减法模块。模拟注册机证明,使用最小串行策略的SNPS能够刻画递归可枚举语言,验证了SNPS在最小串行策略下仍具有与图灵机等价的计算能力。In order to verify the computing performance of the spiking neural P systems(SNPS)with the operational restriction,the min-sequentiality strategy is introduced into the standard SNPS to study its language generation ability.At each step of the calculation,only neurons satisfing the corresponding rules and containing the least number of spikes can be excited for the SNPS working in the min-sequentiality strategy.The relations between the SNPS working in the min-sequentiality strategy and the finite language and the regular language are analysed,and the mapping from the arbitrary multivariate alphabet to the binary alphabet is defined.The SNPS producing the recursively enumerable language is constructed.The addition module and the subtraction module are designed.By simulating the register machine,it is proved that the SNPS working in the min-sequentiality strategy can describe the recursively enumerable language and has the equivalent computing power to the Turing machine under the min-sequentiality strategy.

关 键 词：脉冲神经膜系统 最小串行策略 递归可枚举语言 注册机 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]