英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
Petri网语言再访问
Antony Mazurkiewicz
摘要
在这个文章中，讨论的是地方行为和Petri网的转换。作为一个被应用的正式的考虑同态独异点的变化的工具，它上升到一个连续网络行为的比较和Petri网的版本转换。这个连续的行为和转换语言被同态独异点的意义讨论和比较。首先，原子网络（仅在单一地方的网络）被考虑。它被证明为与上下文无关的连续行为，其次，常规上讲转换行为获得一个连续的同态想象。从这里开始，通过网络语义合成性的性质，这个结果被地方网络和转换网络分开。也就是说连续行为中的交集是一个有限数量的与上下文无关的语言，其次一般的网络是常规的交换行为。他们定期连续的语言子集的网络交换图像和原始的一样。
关键词： Petri网 语言格式 交换性 组合性 可达性
1介绍
本文旨在讨论、分析和比较一些方法的并发系统行为表示。作为一个正式的模型的并发系统中选择的网络,提供一个正式的、足够广为人知的并发性的描述方法。作为一个正式的工具比较行为系统的一些代数结构,如独异点以及它们之间射。系统在这个讨论中扮演一个重要组成部分的组合性原则:建立了属性后简单的结构,结果是更复杂的了。行动组执行序列,集多重集从无关的抽象继承法,并设置访问的主要兴趣。展示强大的一面向代数方法在解决各种问题的离散过程理论,是准备的另一个动机。Petri网讨论的论文网没有所谓的自我循环,即输入任何过渡的地方都是独立设置的输出的地方。
本文如下，首先,所谓的原子网被认为是,即网络只在一个地方。网络三个对象描述介绍了他们的行为,作为连续的行为,包含众所周知的执行序列。接下来,通过交换同态映射这些序列来交换行为,忽视一些排序的操作,最后,通过可达性同态映射执行序列可及集的状态。证明所有执行的原子序列的集合网是一种上下文无关语言。
第二,网络构成的性质,比如行为是构成他们的个人行为,作为一种工具用于一般网分析。证明一般网的执行序列的集合的交集有限数量的上下文无关的语言,它显示了如何接近不可判定性问题连续的语言的问题。然而,使用正则语言的众所周知的事实,十字路口的结果普通语言,事实证明,任意网是常规的交换行为。它有助于证明的可达性问题的可判定性一般网。结束语本文结束。
假定读者熟悉一些基本事实的形式语言和有限自动机理论一方面,和一个(非常受限制的)知识Petri网,另一方面,他们的行为。此外,抽象代数的一些基本信息会很有帮助。
2预备知识
通过使用标准的数学概念，数集{0.1.2...}和{.....，-2，-1,0,1,2...}将被分为Z和N。
任何有限集T的符号将被称为字母。任何有限序列w T是一个符号词/ T,其长度是用|w|;单词长度为0的(空词)用ϵ。所有单词的集合/ T用Tlowast;。连接词的u =(1、2hellip;hellip;n),字w =(1 b 2,hellip;b m),n, mge;0,是词u·w =(1,2,hellip;b、n 1,b 2,hellip;b m)称为与w的连接。逗号分隔符号以及点象征着连接操作通常省略。Tlowast;我们理解所有单词的集合在T .显然,(Tlowast;·ϵ)是一个免费的独异点与T的发电机。词u是词的前缀w。写你le;w如果你是w的前缀。数w | |词的长度是w。Tlowast;子集被称为连续的语言,或简单地说,语言在语言Lsube;Tlowast;说prefix-closed,如果ule;visin;LrArr;uisin;任何语言L 1 L,L 2sube;Tlowast;为语言编写L 1 L 2 { w 1 w 2 | w 1isin;L 1 w 2isin;L 2 }。
上下文无关语法任何四G =(V,T,P,sigma;),V是一组有限的符号,Tsube;V一组终端符号Psube;(Vminus;T)times;Vlowast;有限与元素被称为产品,和sigma;isin;Vminus;T是公理G .给定的上下文无关文法G =(V,T,P,sigma;),关系→sube;Vlowast;lowast;times;V是定义的等价性
w′→w′′hArr; exist;u ′, u′′,v, w : w′=u′v u′′,w′′=u′w u′′,(v, w) isin; P
被称为一步关系在g .调用派生关系在根特表示→lowast;自反转移闭包→。序列的单词(w 0 w 1,hellip;内部,w n)ge;0叫做a derivation w w n的0,如果w我minus;1→w foralli,0 lt;我le;n,w n据说是源自w 0。然后调用n推导的长度。如果w′′来源于w′,写w′→lowast;w′′。我们还应当写(v→w)生产(v,w)isin;p语言。
L ( G ) = {w isin; T lowast; | sigma; → lowast; w}
是上下文无关语言定义的语法g .特殊情况下的上下文无关语法常规语法。上下文免费的语法(V,T,P,sigma;)是常规,如果Psube;(Vminus;T)times;Tlowast;(Vcup;{ϵ})。语言由正则文法生成说是常规的。
3原子网络
定义1：原子网任何命令三=(T、F m 0)比如
T is a finite set (of transitions) ,
F : T minus;→ Z ( valuation ),
m 0 isin; N ( initial value ).
估值是扩展Flowast;:Tlowast;minus;→Z通过设置Flowast;(ϵ)= 0,Flowast;(w T)= Flowast;(w) F(T)和Flowast;(Z)= { Flowast;(w)| wisin;Z }任何tisin;t,t w tlowast;isin;,Zsube;lowast;。为每个wisin;T P(w)lowast;定义条件如下
P (w) hArr; forall; u le; w isin; T lowast; : F lowast; ( u ) ge; 0
L = {w isin; T lowast; | P (w)}
的语言顺序,或者只是语言A组整数Flowast;(L)可达性的L;整数在Flowast;(左)由L可及。
T p = { t isin; T | F ( t ) ge; 0 }, ( set of producers ),
T m = { t isin; T | F ( t ) lt; 0 }, ( set of consumers ),
| A | =
t isin; T
| F ( t )| m 0 , the size of A .
观察到转换tisin;F(t)= 0是可以接受的,上面的定义和正式列为生产商;之后,他们将被证明是有用的在大量的原子组成网,作为过渡,参与行动的原子网但不参与。
例1：Triple X = ({ a , b , c },{( a , 2 ),( b ,minus; 3 ),( c ,minus; 1 )}, 3 ) is an atomic net, with | A | = 9 , T p = { a }, T m = { b , c }
在本节的其余部分原子净=(T、F m 0)与符号T p T m,| |,p将固定和定义为;让L的连续的语言。
3.1连续的原子体系的行为
我们从一些属性的顺序语言L。
建议1：保持所有wisin;L以下属性:
1. F (w) ge; | A |, t 1 , t 2 isin; T , t 1 ̸= t 2 rArr; w t 1 t 2 isin; L,
2. w isin; L , a isin; T p rArr; w a isin; L,
3. t 1 isin; T , b isin; T m ,w b t 1 isin; L rArr; w t 1 b isin; L,
4. b 1 , b 2 isin; T m rArr; (w b 1 b 2 isin; L hArr; w b 2 b 1 isin; L )
证明：显然,Flowast;(w)gt; | |担保P(w t 1 t 2)任意t, t 2isin;t, t 1̸= 2,此后Flowast;(w)足够大确保P(w t 1)以及P(w t 1 t 2)。它证明了1。暗示2表达事实,P(w)意味着P(w)isin;T P。暗示3说,如果P(w b t 1)适用于t 1isin;t, bisin;t m, P(w t 1 b)。暗示4是显而易见的:改变1 b 2 b 2 b 1 b的1,b 2isin;T m保留P的有效性(w 1 b 2 b)和P(w b 2 b 1)。
建议2：Let w, w 1 ,w 2 isin; L . 然后
1. P (w t ), t isin; T rArr; P (w) ,
2. P ( u ), u isin; T lowast;m rArr; 0 le; Flowast; ( u ) le;m 0 ,
3. P (w 1 w 2 ), a isin; T p rArr; P (w 1 a w 2 ),
4. P (w 1 b w 2 ), b isin; T m rArr; P (w 1 w 2 )
证明：声明1表达的prefix-close { w | P(w)},这是显而易见的。声明2遵循直接从的定义P(w),保证Flowast;(u)所有ule;ge;0 w。奖学金(w 1 w 2)是有效的,在more P(w 1 w 2)是有效的,奖学金(w 1 b w 2)是有效的,P(w 1 w 2)是有效的,为所有w 1 w 2isin;L,这证明了3和4。
定义2：让一个原子净上面定义为,{lang;krang;|minus;|的|le;kle;| | }cap;T =empty;。语法G =(V, T, P, sigma;),这样
V = {lang; k rang; | minus;| A | le; k le; | A |} cup; T ,
P = {lang; 0 rang; → ϵ} cup; {lang; F ( t )rang; → t | t isin; T } cup; ( terminating )
{lang; k rang; → lang; n rang; | k le; n le; | A |} cup; ( increasing )
{lang; k n rang; → lang; k rang;lang; n rang; | lang; k n rang; isin; V , k ge; 0 or; n le; 0 }, ( splitting )
sigma; = lang;minus; m 0 rang;
将被称为原子净的顺序语法吗
在本节中象征→→(步骤)和象征lowast;(推导过程)将被用作相关语法G上面定义
引理1： w ′′isin; V lowast; , 0le; m le;|A|:sigma; lowast;w ′w′′rArr;sigma;→lowast;w ′lang; m rang;w′′
3.2减少原子网的行为
在本节中,我们讨论一些替代的描述原子网的行为。让原子净被定义为前一节,让所有有关概念表示如上所述。如上所述,用l .我们的语言开始与原子网络语言的一个子集被称为语言的净减少。减少语言的基本属性是:(1)相同的可达性设置为原始语言;(2)降低语言的规律。
定义3：让一个原子净上面定义为。减少语言的所有单词的集合wisin;L这样 bisin;T m v ble;w
F lowast; (v) le; | A |.
在接下来让R表示原子净的语言。
命题4：w isin; R hArr; exist;w ′ isin; T lowast; ,w ′′ isin; T lowast;p w = w ′ w ′′ isin; L , forall; u le; w ′ : F lowast; ( u )
上述命题提供了一个显式的形式在R 3描述词的定义由两个词组成的w′w′′,Flowast;(u)le;| |任何缀u的第一,第二个包含专门生产商(过渡积极的估值)。在续集将帮助减少语言的讨论可达性问题
命题5：让wisin;l .下列语句是有效的:
1. ϵ isin; R;
2. w isin; R , a isin; T p rArr; w a isin; R;
3. w a isin; R , a isin; T rArr; w isin; R.
4. u le; w isin; R rArr; u isin; R
.
3.3原子网的交换行为
让一个=(T,F,m0)是原子净固定这一节的其余部分,和L A的顺序语言说kisin;N由在m的步骤中,可获得的exist;w isin;L: |w| le;m, k=Flowast;(w).说,wisin;Tlowast;单价的,如果任何前缀u,vle;wF lowast;(u)= F lowast;(v)rArr; u =v.
引理2：对于任何词wisin;L有单价的u Lisin;Flowast;(w)= Flowast;(u)和u | |le;| |。
证明：让Flowast;(w1uw2)= k,Flowast;lowast;(w1)= F(w1u)。那么F(w1w2)= k和| w1w2 |le;| w1uw2 |。因此,这个词你可以从w1uw2保持F的值删除lowast;(w1uw2)不变。显然,w1w2isin;L。证明完成重复这一点
引理3：让wisin;Tlowast;单价的词,Flowast;(u)le;k ule;w。然后|女|le;k。
证明：假设Flowast;(w)le;k, kisin;N wisin;Tlowast;单价的w。如果w | | gt; k,然后由狄利克雷原理(也称为鸽笼原理)会有至少两个不同的前缀ule;w, vle;w与Flowast;(u)= Flowast;(v),这与一价的w。
证明。假设wisin;L Flowast;(w)= kge;0。然后是w′isin;F R这样lowast;(w′)= kge;0。它遵循从引理2有单价的词uisin;F R这样lowast;(u)= k。减少语言的定义R单价的词的长度u′,Flowast;(u′)le;| |不大于| |,和单价的词的长度u′′isin;F T plowast;这样0le;lowast;(u′′)le;k不大于k。自从你| |le;u′| | | u′′|,我们得到你| |le;| | k。从u Risin;sube;L,完成证明。
定理6：可达性原子网可决定的。
4普通的Petri网
在本节中,我们将为原子网一般的成果,众所周知的地方/过渡网,或P / T网。首先,一些必要的定义。接下来,组合性原则将使制定可能讨论复杂网通过原子的性质。最后,通过结合投影的性质和换向同态。我们证明基本事实一般网,即语言类型和可达性。
定义5：通过一般净我们应当理解任何四N
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[146731]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
