数值P系统的计算性能研究

来源 :华中科技大学 | 被引量 : 0次 | 上传用户:cclone
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
膜计算是自然计算的一个分支,主要研究如何基于细胞的结构和功能(包括组织、器官、细胞群和大脑中细胞间的通信与合作机制)抽象出计算模型,并分析模型的计算能力和计算效率。膜计算领域的计算模型称为膜系统或P系统。膜计算领域的一个最重要课题就是研究各种膜系统的计算能力。数值P系统是一种重要的膜系统,对影响其计算能力的因素的研究具有重要的理论意义。  本文主要研究数值P系统各组成要素对其计算能力(包括产生数值和语言)的影响。构成一个数值P系统的主要要素有膜结构,膜中数值变量和演化规则,其中演化规则由生产函数和分配协议构成。本文主要考察的因素有规则的运行方式(串行、全并行和1-并行),酶变量的数量,阈值控制条件,函数型分配协议系数,变量的迁移特性等。主要工作如下:  研究了工作模式对酶数值P系统计算能力(产生数值)的影响。酶数值P系统在全并行和1-并行工作模式下已经被证明可以达到通用,但在串行模式下能否达到通用还是个公开问题。本文证明了酶数值P系统在确定型串行工作模式下能够达到计算通用性,改进了一个已知的非确定型数值P系统的通用性结果(在系统其他参数不变的情况下,所用的膜数量更少,生产函数所用变量数目更少)。上述结果表明酶数值P系统的计算能力对工作模式具有鲁棒性,即不管采用何种工作模式酶数值P系统都能达到通用性。  研究了酶变量的数量对酶数值P系统计算能力的影响。酶数值P系统在全并行和1-并行工作模式下已经被证明可以达到通用,但系统最少使用多少个酶变量就能达到通用还没有相关研究。本文证明了对于酶数值P系统作为识别装置,在全并行和1-并行运行模式下最少只要1个酶变量就能达到通用;作为产生装置,在1-并行模式下,最少2个变量可以达到通用。这些结果说明,系统的计算能力对酶变量数量具有鲁棒性,即使将酶变量的数目减少到1个系统仍然可以达到通用。  研究了带阈值的规则对数值P系统计算能力(产生数值)的影响。对数值P系统的规则没有任何限制时在全并行和1-并行下计算能力能否达到通用是个公开问题。本文证明了带阈值的数值P系统在全并行和1-并行两种工作模式下都能够达到通用性,即使把它们的膜数量限制为1,生产函数限制为线性函数。以上结果表明对规则的使用加阈值控制策略能够增加系统的计算能力。  研究了函数型分配协议系数对数值P系统计算能力(产生数值)的影响。数值P系统的分配协议系数为常数时计算能力能否达到通用是一个公开问题。本文将常数系数扩展到函数,分配系数函数的函数值决定变量分得的份额,所得到的系统称为带动态分配协议的数值P系统。证明了带动态分配协议的数值P系统在全并行工作模式下,使用常值函数作为生产函数,单变量线性函数作为分配系数函数,只含一个膜的系统可以达到通用。而在串行工作模式下,生产函数为至多含一个变量的线性函数,分配系数为至多含两个变量的线性函数,只含一个膜的系统也可以达到通用。这些结果表明分配协议系数由常数拓展到函数可以增加系统的计算能力。  研究了数值P系统产生语言的能力。系统产生语言的能力是研究系统计算能力的基本问题之一。目前还没有相关文献研究数值P系统产生语言的能力。本文给出了数值P系统产生语言的定义,并研究了数值P系统,酶数值P系统,纯酶数值P系统在1-并行工作模式下产生语言的能力,以及上述系统产生的语言与有限语言,正则语言,上下文无关语言以及递归可枚举语言之间的关系。  研究了变量的迁移特性对数值P系统计算能力(产生数值和语言)的影响。把一般P系统符号对象可以在膜内外迁移的特性引入到数值P系统,提出了带迁移变量的数值P系统,并研究了其作为数值产生器产生数集和语言产生器产生语言的能力,证明了其作为数值产生器可以达到通用性,作为语言产生器,将其产生的语言与乔姆斯基层次中的语言进行了比较,并刻画了递归可枚举语言。获得的结果表明,不论是对数值P系统还是对酶数值P系统而言,变量可以迁移的特性都能提高原系统的计算能力,如系统使用更少数量的膜,使用更简单的生产函数(对多项式而言,次数更低,所含变量个数更少),使用更少数目的变量就能够达到通用。
其他文献
为了使不同功能的温泉池发挥最佳疗效以及降低功耗,温泉度假村必须对每一个温泉池的水温进行监控,让多点不同温度需求的温泉池在设定的温度值进行恒温保持。以往的温泉水温检测
气动弹性研究的是弹性物体的结构动力学问题,气动弹性现象是气动力、惯性力与弹性体相互作用下产生的。由于结构不是绝对刚度的,具有一定的弹性,当来流风速到某个临界值时,结
电动助力转向系统EPS(Electric Power-assisted Steering)是近几年迅速发展的一项汽车性能提升的新技术。与传统机械和液压助力转向系统对比,电动助力转向系统是根据作用在方
随着监控技术的发展,将机器视觉融入到监控技术中的智能视觉监控系统已成为监控技术新的发展方向。智能视觉监控技术涉及了机器视觉、图像处理、模式识别和人工智能等众多领
近年来随着全球范围内人口老年化趋势日益加剧,可穿戴型助力机器人已经成为重点的研究领域之一,膝关节助力机器人作为可穿戴型助力机器人的重要组成部分,科学家对其技术的开发和
我国是一个农业大国,耕地面积约20亿亩,但人均耕地面积仅有1.4亩,人多地少的矛盾突出。随着人口的不断增加及耕地的减少使得我国粮食增产问题面临着巨大的挑战,在耕地面积有限的
本文是在省部共建项目“模型黄河网络图像监测与处理系统”的资助下完成。随着计算机技术和图像技术的发展,基于图像分析及其相关技术的测量方法在河工模型试验中成功实现了
近年来,各种管道流体运输系统(石油化工管道、城市排水管道、自来水管道等)在人类生产和生活中发挥着越来越重要的作用,相比与其它运输系统,它具有高效、安全、经济等多方面优势。
随着科学技术的不断进步,一些大型设备、精密仪器已经广泛地应用于工业、石油、化工等各个领域。这些设备的安全和质量关系着整个企业生产过程的运行状况,对整个国民经济的发
自行车机器人是近年来机器人学术界提出的一种全新的智能交通工具。它具有方便、快捷、灵活性强等特点,发展前途被广泛看好。自行车机器人动力学特征较为复杂,其两轮纵向布置