上下文无关语言的可重复序列及其性质

通过分析下推自动机的运行规律和特点,提出上下文无关语言的可重复序列的概念,将其划分为平衡重复序列、增重复序列、减重复序列三类;研究了这三类可重复序列在下推自动机的状态转换图中的结构表现和性质,通过分析下推自动机状态转换图中标注回路与可重复序列之间的关系,给出求解可重复序列的计算方法;证明了不同类型的可重复序列对上下文无关语言性质的影响,利用可重复序列揭示了上下文无关语言的Pumping引理的本质特征,并给出正规语言判定的一个充分必要条件.     

Petri网语言表达式及其求解算法

Petri网语言是描述网系统动作序列的集合.为了给出一个网系统语言的形式描述,基于Petri网的状态转换图,分析了Petri网的行为特征,定义了α闭包表达式和Petri网语言表达式,给出了求解Petri网语言表达式的算法,为Petri网语言的形式化描述和分析提供了一种新方法.     

Web服务自动化测试技术

赋时Petri网为装配序列规划提供了有效的建模方法,但其在求解最优装配序列时受到组合复杂性的严重制约。零压缩二叉决策图(ZBDD)是处理大规模组合集合和0-1稀疏向量的一种有效符号技术,能够有效缓解组合爆炸问题。将赋时Petri网与ZBDD结合起来,给出了一种求解装配序列最优解的有效方法。首先通过转换算法将赋时Petri网转换为等价的普通Petri网,接下来给出普通Petri网可达状态及迁移引发函数的ZBDD表示方法,最后基于ZBDD给出最优装配序列求解算法。实例验证表明,该算法在求解过程中通过隐式符号操作实现了Petri网的可达状态搜索,有效缓解了计算过程中的组合复杂性。     

类S—图的语言性质分析

1 引言 Petri网作为系统模拟和分析的工具己得到广泛的应用。Petyi网一个变迁序列可理解为一个字符串,字符串集合为一种语言。所有可能发生的变迁序列的集合表征了一个Petri网的运行特征,可用网中可能出现的变迁序列来分析Petri网的性能。Hack和Peterson最早从事这方面的研究。Hack在文[3]中讨论了网模型的计算能力,指出带抑止弧增广Petri网与图灵机在计算能力上是等价的,从而充分显示了Petri网模型的表达能力。文[4]给出了并发正规表达式的概念,并证明了井发正规表达式与Petri网的语言描述能力等同。文[5]给出了Petri网语言与形式语言关系之间的一个清楚的刻画,并给出了从代数角度判别语言属性的充分必要条件。文[6]研究了语言的识别问题,并给出了基于网语言的网活性刻画。     

有界Petri网的最小化化简

给出了Petri网的语言等价性概念和有界Petri网的最小化概念;证明了有限状态自动机、有界Petri网、正规文法的等价性,给出了它们之间等价转换的算法;分析了有界Petri网的化简过程,并给出了有界Petri网最小化化简的算法,为有界Petri网的自动化化简提供了方法。     

袋自动机

提出了袋自动机模型和袋语言的概念,并给出了袋自动机的状态转换图;分析了袋语言重复序列在状态转换图中的反映,并划分为不变重复序列、增重复序列、减重复序列和传递重复序列,给出了袋语言的结构特性;研究了袋语言类同Chomsky文法体系中各型语言的关系,证明了正规语言类是袋语言类的真子集,袋语言类是上下文有关语言类的真子集,而袋语言类同上下文无关语言类是两个相交但互不包含的语言类,即存在不是上下文无关语言的袋语言,也存在无法用袋自动机产生的上下文无关语言.     

语言表达式到Petri网模型的转化及其算法

已知一个语言的表达式,直接构造产生该语言的Petri网模型是Petri网语言理论中一个重要问题.本文分析、研究同步交错正规表达式中各种运算与Petri网模型的对应转换关系,分别给出正规表达式、α闭包表达式到Petri网模型的转换方法;定义了Petri网的有界覆盖合成运算,研究有界覆盖合成网的语言性质,给出将同步交错正规表达式转换为Petri网模型的算法,从而实现了语言表达式到Petri网模型的等价转化.     

多功能流水线调度的Petri网分析

在单功能流水线的Petri网模型[1]基础上，给出了一种基于时延Petri网的多功能流水线建模方法。并给出其资源状态转换图来反映其运行过程中资源的使用状况，利用这种资源状态转换图可求出其任意输入序列的最佳调度方案。     

作战事件跟踪描述建模及验证方法研究

为了对体系结构设计中的作战事件跟踪描述进行建模分析,提出了用扩展时序图模型对作战事件跟踪描述进行建模的方法。定义时序图的生命线为时间消息,研究了时序图模型与Petri模型之间的同构关系,以此为依据给出了时序图转换为Petri网的算法。在此基础上,研究了扩展时序图和对象Petri网之间的转换算法,并处理了扩展时序图中的自环消息特例。最后,结合防空作战过程给出该方法的一个应用案例。     

Petri网展开图法的分析和应用

Petri网的展开图是一种特殊的并发系统状态空间搜索方法，它不需要重复考虑并发事件的所有可能的交集，从而大大缩减状态空间爆炸给验证分析带来的空间复杂度和时间复杂度。使用展开图分析Petri网的行为属性与传统的Petri网分析方法相比，具有自己的特点。该文首先介绍了Petri网展开图的构造算法，在此基础上使用展开图分析方法对一个典型Petri网的活性，有界性和可逆性等行为属性进行了分析，并与传统的Petri网分析方法作比较。     

Universal petri net

A universal inhibitor Petri net executing an arbitrary given inhibitor Petri net is constructed. An inhibitor Petri net graph, its marking, and transition firing sequence are encoded as 10 scalar nonnegative integer variables and are represented by the corresponding places of the universal net. An algorithm using only these scalar variables and executing an arbitrary inhibitor net is developed based on the state equation and is encoded by the universal inhibitor Petri net. Subnets that implement arithmetic, comparison, and copy operations are employed.     

标注Petri网中的最小初始标识估计

为获得制造系统初始化时的最小资源以实现最优资源分配,利用标注Petri网对系统进行建模,并研究标注Petri网的最小初始标识估计问题。给定一个标注Petri网,在不可观测变迁组成无环子网的情况下,基于动态规划提出一种新的最小初始标识估计算法。在观察到给定的标注序列后,放宽不可观测变迁发生个数的限制,并根据该算法构建节点的演化过程。当出现相同的发生数向量时,仅保留当前极小的初始标识估计,并通过节点的演化过程对极小初始标识估计的托肯总数进行对比。为验证算法的有效性,给出一个制造系统的标注Petri网模型实例,最终得到的最小初始标识为［1000］^T,且对应的变迁发生序列为t₁t₃t₄t₆,满足给定标注Petri网的结构要求。实验结果表明,与传统基于动态规划的算法相比,该算法获得的最小初始标识估计具有更小的托肯总数。     

Deadlock-Freeness Analysis of Continuous Mono-T-Semiflow Petri Nets

Most verification techniques for highly populated discrete systems suffer from the state explosion problem. The “fluidification” of discrete systems is a classical relaxation technique that aims to avoid the state explosion problem. Continuous Petri nets are the result of fluidifying traditional discrete Petri nets. In continuous Petri nets the firing of a transition is not constrained to the naturals but to the non-negative reals. Unfortunately, some important properties, as liveness, may not be preserved when the discrete net model is fluidified. Therefore, a thorough study of the properties of continuous Petri nets is required. This paper focuses on the study of deadlock-freeness in the framework of mono-T-semiflow continuous Petri nets, i.e., conservative nets with a single repetitive sequence (T-semiflow). The study is developed both on untimed and timed systems. Topological necessary conditions are extracted for this property. Moreover, a bridge relating deadlock-freeness conditions for untimed and timed systems is established.     

Polynomial-time algorithm for the legal firing sequences problem of a type of synchronous composition Petri nets

As far as we know, the testing problem of legal firing sequence is NP-complete for gener-al Petri net, the related results of this problem on the polynomial-time solvability are limited only to some special net classes, such as persistent Petri nets, conflict-free Petri nets and state machine Petri nets. In this paper, the language properties of synchronous composition net are discussed. Based on these results, the testing algorithm polynomial-time complexity for legal firing sequence is proposed. Therefore, net classification of polynomial-time solvability for testing legal firing sequence is extended.     

时间Petri网的随机模拟

模拟是Peri网进行系统分析的常用方法之一。由于时间Petri网采用时间区间来描述变迁实施的时间范围,因此变迁的实施时间点在区间内是不确定的。提出了时间Petri网的随机模拟方法。该方法在变迁开始使能时,根据某种随机分布确定实施区间内的实施时间点;然后基于模拟仿真的实验数据,运用统计分析方法及算法,构造时间Petri网状态类树,计算变迁实施区间及实施概率,为时间Petri网的系统模拟提供了一种新的探索途径。     

Reachability analysis in T-invariant-less Petri nets

An algorithm for reachability analysis in place/transition Petri nets having no transition invariants (T-invariants) is proposed. Given a Petri net with initial and target markings, a so-called complemented Petri net is created first that consists of the given Petri net and an additional complementary transition. Thereby, the reachability task is reduced to computation and investigation of those minimal-support and linearly combined T-invariants of the complemented Petri net, in which the complementary transition fires only once. Then, for each T-invariant with a single firing of the complementary transition, the algorithm will try to create a reachability path from the given initial marking to the target marking.     

Proof procedure and answer extraction in Petri net model of logicprograms

A proof procedure and answer extraction in a high-level Petri net model of logic programs is discussed. The logic programs are restricted to the Horn clause subset of first-order predicate logic and finite problems. The logic program is modeled by a high-level Petri net and the execution of the logic program or the answer extraction process in predicate calculus corresponds to a firing sequence which fires the goal transition in the net. For the class of the programs described above, the goal transition is potentially firable if an only if there exists a nonnegative T-invariant which includes the goal transition in its support. This is the main result proved. Three examples are given to illustrate in detail the above results