|||
报告题目:谈谈无穷Petri网。
报告人:郝克刚,西北大学信息与技术学院教授。
报告时间:2011.8.20.
报告地点:北京外国专家大厦二楼多功能厅。
内容简介:
一般在讨论和应用Petri网时,总假定Petri网的位置和转移集合是有穷集。如果允许它们是无穷集,则称其为无穷Petri网。不要以为所有的无穷Petri网系统都是难以捉摸,不可执行的。如果我们限制所有的转移的入弧数和出弧数是有穷的,这样转移是否可激发就能够判定,而且激发后转移托肯的动作也是可以完成的。如果再加上每一步只允许执行有穷个互不冲突转移的激发的限制。无穷Petri网系统就可以同有穷Petri网系统一样地执行。我们把这样的无穷Petri网的子类称为可执行无穷Petri网。
报告着重介绍的是可执行无穷Petri网的一个子类,称为递归无穷Petri网。所谓递归是指:无穷Petri网由两个有穷Petri网(一个称基始一个称递归模版),按照如下的方法来动态地构造。以基始Petri网为基础,然后一个一个地同由递归模版逐个生成的具有同样结构的有穷Petri网,按照一定的方法串连起来。具体说就是用共享接口中的位置和转移的方法来动态地构造。系统的初始标识也按类似的方法构造。我们研究了这类网的某些属性。
有趣的是我们可以严格地证明,递归无穷Petri网同图灵机是等价的。即图灵机的结构以及操作执行过程,可以完全用递归无穷Petri网系统来描述和表达。从而解决了长期困惑我们的,无穷Petri网同图灵机是如何等价的问题。报告将简要介绍证明的思路。
作此报告,是想引起大家研讨这些理论问题的兴趣,听听同行们的看法、意见和建议。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-5-21 19:01
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社