没有合适的资源?快使用搜索试试~ 我知道了~
真正并发处理确定性资源消耗的多子集方法
可在www.sciencedirect.com在线获取理论计算机科学电子笔记286(2012)307-321www.elsevier.com/locate/entcs可消耗资源多子集上的真正并发进程语义Dan Teodosiu1巴黎中心数学科学大学Paris Diderot(Paris 7)75205 PARIS CEDEX13,France摘要本文开发了一个真正的并发语义的方法,并发性是概念上独立的非确定性,允许描述的递归进程访问消耗性资源的确定性并发行为。过程语义是基于新的相干完整和素代数域的真实和复杂的多pomset。我们研究的过程语言包含几个确定性的定量过程操作符,即重命名,隐藏,限制,串行和并行操作符,以及递归操作符。所展示的确定性结构运算机器产生线性和复杂的运算语义。构造了一个复合指称语义,它在复杂的多pomsets环境中使用一个功能域。 所提出的语义工作的鲁棒性建立证明指称语义是完全抽象的线性和复杂的操作语义。关键词:进程演算,真并发,资源,消耗,量化,pomset,指称语义,结构操作语义,完全抽象。1介绍Hennessy Plotkin [6]的开创性工作已经展示了如何使用幂域假设选择操作符是语言的一部分,并行性被简单地简化为交错和选择,从而将非确定性引入语义模型。在本演示中,我们遵循一种真正的并行和并发方法,避免使用选择和非决定论。因此,我们依赖于真正的并发性,这激发了大量的领域理论方法。这主要是由于Winskel [12]的主要事件结构是提供合适模型来表达真正并发进程组合的域。1电子邮件:dan. wanadoo.fr1571-0661 © 2012 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2012.08.020308D. Teodosiu/电子笔记理论计算机科学286(2012)307然而,据我们所知,唯一真正的并发语义方法,实际上已经开发了一个操作和匹配的指称编程语义,允许无限过程组合子以及递归,起源于DiekertGastin [2],Gastin Teodosiu [5]和Gastin Mislove [4]的工作底层的指称模型是Pratt [9]提倡的pomset,虽然是特定的事件结构,但允许简单地表达真正的并发过程组合。它的直觉是基于任何环境中的过程和资源之间的吸引人的交互,这也是过去几十年来推动计算机科学还应该注意Pym Tofts [10]的相关自动机理论中的一个新趋势,正如最近关于加权自动机的专著所强调的那样,包括为转换赋予权重,这些转换表示它们的成本或消耗,并将这些概念扩展到公认的单词和语言。经典的自动机理论可以通过考虑单位权重来恢复,这就是为什么加权视图更加通用,为工程和经济中的新应用开辟了道路目前的过程语言结合了上述真正并发的方法在指称方面的加权自动机的操作方面的看法。 到为此,用有界或无界的时间或消耗的资源量来量化指称模型和操作转换规则的标记。量化需要用多资源集的代数(被看作是扩展正实数上的向量)来代替以前使用的 此外,它导致定义运算符,其定量语义丰富了严格考虑的运算符(串行,并行),以及具有新的定量语义(重命名,隐藏,限制,递归)的运算符。我们的语义在几个技术方面与以前的方法不同。首先,将进程表示为复杂的多pomset依赖于实部和消耗部,这允许平凡地检查消耗的互换性和连续性。其次,复域上的新前缀偏序极大地简化了证明,允许只检查实部的复连续性。最后,递归的语义依赖于两个阶而不是一个阶的连续性。本文的结构如下。第2节回顾了部分订单的基本事实。第三节介绍了实复复复域。第4节介绍了过程语言并定义了消费语义。第五节给出了一个确定性结构的操作机器,它产生了线性和复杂的操作语义。第6节是专门的组合指称语义使用功能域的环境中复杂的多pomset。第7节给出了线性和复杂操作语义的指称语义的一致性和完全抽象的主要结果。D. Teodosiu/电子笔记理论计算机科学286(2012)307309(1)F(JF(Y)Kmp(x)是有向的,且x=Kmp(x)对所有x∈X。就社区首席采购干事而言,Y)=感兴趣的读者可以在[11]中找到我们结果的完整版本。2偏序关于详细的论述,我们可以参考Abramsky Jung的介绍 [1]。偏序(PO)是一个对(X,≤),其中≤是X上自反、反对称和传递的二元关系。一个子集Y<$X是有向的(相干的)i <$它是非空的,并且对所有x,y∈Y,存在z∈Y(z∈X)使得x≤z,y≤z。任何有向集都是相干的。(X,≤)是相干完备PO(CCPO)(有向完备PO(DCPO)),其中每个相干子集(有向子集)都有一个最小上界.任何CCPO都是DCPO一个元素x∈X是素(紧)i ∈ X,对于所有有最小上界的(有向)子集Y<$X,x≤Y意味着x≤y,对于某些y∈Y。 一组所有X的素(紧)元在y∈X以下记为Prm(y)(Kmp(y))。 偏序(X,≤)是p-代数i <$x=Prm(x),对所有x∈X. 它是k-代数的p-代数性也包含k-代数性。一个k-代数DCPO被称为(Scott-)域。 映射F:(X,≤)→(XJ,≤J)is(Scott-)c是所有有向集Y<$X的唯一i,使得Y存在,有限序数的集合(即最小无限序数)用ω表示。3实数和复数多复调我们用+表示正实数的集合,用+=+<${∞}表示正扩充实数的集合。符号和保留供以后使用。我们在这一节中固定了一个可数的资源集R。 字母表就是集合多组资源=R→+。我们定义0,∞ ∈ 0(α)= 0,∞(α)=∞,对所有α∈ R. 这组操作是R=\{0}。例如,一个动作对一个资源所附加的多重性度量了所消耗的时间。时间的概念也可以用数量来代替,而消费这个词也可以用生产来代替。 例如,如果R={A,B,C}则分别消耗A、B和C的3.5、5.7和7.3时间单位的动作由多集合3表示。5 A + 5。7个B + 7。3C.具体的例子可能来自计算机科学(一个动作消耗5个处理器,10个通道和2个内存时间单位)或工作流程管理(一个动作消耗100个人,5个工具和10个对象时间单位)。在我们定义的分量顺序≤×,补集<$:→,sum +:×→,最后一点:×→,supremum:×→和偏斜差\:×→,其中对于所有n,m∈+,我们设置n= ∞如果n= 0,如果n= 0,则n = 0,如果n =∞,则n\m= ∞,如果n∞且m=∞,则n\m=0,n\m =(n-m)<$0如果n,m∞.对于a,b∈使得b≤a令a-b=a\b。 对于a,b∈,我们定义independenceabiab= 0.310D. Teodosiu/电子笔记理论计算机科学286(2012)307对于a∈=R →+和S∈R×R →+,我们设S(a)=aS为向量-矩阵乘法.重命名集合RR×R →+定义为:S∈Ri <$(a/=0 =<$S(a)/=0 for alla∈)和(a<$b=<$S(a)<$S(b)forala,b∈).3.1实多复摆集的域一个实多标号偏序是一个三元组(E,≤,ρ),其中(i) 同步关系≤E×E是事件集E上的偏序,满足过去有限性条件{f∈E|对于每个e ∈E,f≤e}是有限的,(ii) 事件标号ρ:E→R满足过同步条件ρ(e)<$ρ(f)/= 0 =εe≤f或f≤e,对每个e,f∈E.一个实多序集是一个实多标号偏序(E,≤,ρ)的同构类[E,≤,ρ]。实多重pomset的集合表示为。一个有限的多pomset是一个多pomset,其事件集是有限的。有限多pomsets的集合表示为。空的多pomset是0= [,,]∈。对于所有的a∈R,我们定义了作用集a=[({n},{(n,n)},{(n,a)})] ∈.同步关系反映了多序集事件之间的时间(或因果)顺序。过去的有限性条件是一个技术性假设,它将定义限制在实多首字母集,但如果希望处理transfinite多首字母集,则可以放宽。过同步条件等价于这样一个事实,即对于每个资源,消耗它的事件是顺序化的(完全有序的)。 特别地,它意味着多pomset没有自动并发,也就是说,为所有a∈R,则集合ρ−1(a)={e∈E|ρ(e)=a}的全序为≤。 出现的次数||a:→ω + 1的a∈R定义为对所有x∈|a = ord(ρ −1(a),≤ π ρ −1(a)× ρ −1(a))≤ ω,这是与≤在ρ −1(a)上诱导的良序相关的序数。|a= ord(ρ−1 (a), ≤ ∩ ρ−1 (a) × ρ−1 (a)) ≤ ω,that is the ordinal associated with the well-order induced by ≤ on ρ−1 (a).为了避免繁琐的同构证明,我们定义x=(E,≤,ρ)的标准表示为唯一的同构实多标号偏序x∈=(Ex,≤x,ρx),使得(i) E x=φ x(E)={(a,n)|a∈R且n<|X|a}R×ω=,(ii) (a,n)≤x(a,m),对所有a∈R和n≤ m<|X|一(iii) ρ x(a,n)=a,对所有a∈R和n<|X|a.F 的 x ∈ 中 的 过 去 是 ↓xF={e∈Ex|f : e≤xf∈F}. x∈F 的 限 制 条 件 为x/F=[Ex<$F , ≤x<$F×F , ρx<$F×R].对 于 所 有 的 x , y∈ , 定 义 为 x≤yi∈Ex=↓yEx和x=y/Ex。下一个定理表明( ,≤)是一个有趣的语义域。定理3.1(,≤)是一个p-代数CCPO,因此它是一个(Scott-)整环。D. Teodosiu/电子笔记理论计算机科学286(2012)307311ΣªRª|u ª x, u−1x =0}.r的线性化集为Lin(x)={u∈N字母表alph: → P( )定义为所有x∈ 通过alph(x)={ρ x(e)|e∈E x}。消费的缺点:→对于所有的x∈cons(x)=e∈Exρ x(e)。可以证明cons:(,≤)→(,≤)是连续的。对于x,y∈我们定义独立性x y i cons(x)cons(y)。无限消费consinf:→对所有x∈和α∈ R定义为:如果cons(x)(α)= ∞,则consinf(x)(α)= ∞,否则consinf(x)(α)= 0。我们需要在后面的定义。 对于a∈R和x∈满足 作用前缀a≤x令作用余数为a−1x=x/(Ex\ {(a,0)})。 让0将空字符串表示为- 是的 对于u∈ 且x∈我们定义线性前缀Ru_x和线性剩余uRx对u的感应:• 设0x和0−1x=x,• 对于a∈R,令ua<$xi <$u<$x,a≤u−1x,且令(ua)−1x=a−1(u−1x)。我们注意到,对于任何a∈R<$且x∈,我们有axi<$a≤xi<$x包含一个标记为a的最小事件,所以在这种情况下,前缀和线性前缀关系重合。(,≤)的主要缺陷是它不适合定义连续性,我们的过程语言的操作符的连续表示,因为例如顺序组合不是单调的(因此,不是连续的)。这并不奇怪,因为字符串的顺序组合(连接)对于前缀顺序来说已经不是单调的了,这在示例中可以很容易地看到a≤a;aJ且b≤b;bJ但a;b/≤(a;aJ);(b;bJ)除非aJ为空。3.2复集域我们通过引入复多子集域克服了上述障碍.复集是一对x=(r,R),其中r∈是一个实复复集,R∈是一个复资源集,使得cons(r)≤R.复域集的集合表示为。多序集r记为Re(x),称为x的实部。多重集R用cons(x)表示,称为x的消费部分。x∈的虚部为Im(x)= cons(x)−cons(Re(x))。如果它的虚部Im(x)为零,则称复集x为终止的.注意,由于关于∞和差分算子的约定,我们有consinf(Re(x))≤Im(x)。复杂多pomset的第一个组成部分是描述过程的观察部分的真实多pomset,而第二个组成部分是多集合表示进程在其执行期间实际消耗的配额的资源。对于所有的(r,R),(s,S)∈,通过(r,R)≤(s,S)惠r≤s和R=S定义了前缀。这里的基本思想是,我们通过让过程的可观察部分r≤s增长来增加关于过程的信息,同时保持配额R=S−1312D. Teodosiu/电子笔记理论计算机科学286(2012)307øø≤可以在执行期间消耗。下一个定理表明( ,≤)是一个合适的语义域。定理3.2(,≤)是一个p-代数CCPO,因此它是一个(Scott-)整环。我们稍后需要 根据定义。对于u∈且x∈ 我们将线性前缀扩展u我的世界RRe(x)和线性余数,u−1x=(u−1Re(x),cons(x)−cons(u))。(,≤)的主要优点是它允许为我们语言的所有过程算子定义内部和连续的表示4过程语言我们在下面固定一个可数的常数集C和一个不相交的可数集变量V。资源的集合是R=C V。常量操作集为C=(C →)\ {0}<$R。术语L的语言由以下BNF样式语法p::=跳过|C|S(p)|pT|pT|p·p|p≤p|X|rec x.pC对所有的c∈C,S∈R,T∈,C∈R,x∈ V。这里,SKIP是空进程,c是常量操作,S()通过S重命名,·是串行合成,是在C中的通道上同步的并行合成,Cx∈V是一个变量,rec x。是x上的递归闭项语言Lc是没有自由变量的项的集合过程项p∈ L的消耗量Cons(p):V→对所有τ∈V归纳定义为:缺点(跳过)(τ)= 0Cons(c)(τ)=c Cons(S(p))(τ)=S(Cons(p)(τ))Cons(p T)(τ)= Cons(p)(τ)\TCons(p<$T)(τ)= Cons(p)(τ)<$TCons(p·q)(τ)= Cons(p)(τ)+Cons(q)(τ)Cons(p≤q)(τ)= Cons(p)(τ)<$Cons(q)(τ)CCons(x)(τ)=τ(x)Cons(recx.p)(τ)= lfp ≤R. ({x}+Cons(p)(τ[x<$→R]))对于τ∈V,我们定义τ[x<$→R]在所有自变量上都与τ相同,除了x被赋值为R。对所有α∈R定义了特征映射{x}∈对于αx,{x}(α)= 0,对于α=x,{x}(α)= 1。 可以从结构上看,关于p∈ L上Cons(p):(,≤)V→(,≤)连续的归纳法。 因此,上述定义确定了组合消费语义Cons:L →((,≤)V→(,≤))。D. Teodosiu/电子笔记理论计算机科学286(2012)307313RτUAuRuτττττJττττp\øττττr∈P,我们有Er=E由EP=E和≤P={≤r|r ∈ P}。的对于任何固定的E集合P的交P使得对于所有−τ→τJτ5操作语义表1给出了我们的确定性结构运算机的转换规则,其中我们令c∈C,T∈,C∈R,x∈ V,p,pJ,q,qJ∈ L,a∈R∈{0},τ∈V. 像往常一样,p [q/x]表示从p得到的项,用q替换所有出现的变量x。注意,递归是以一种可观察的方式建模的,每次展开都会产生被递归的变量作为观察,该变量随后可能被重命名或隐藏。u对于u∈ 且p,PJ∈ L,τ∈V,设线性转移p=φPJ是诱导的,由u的长度定义,0pJip=pJ,τ• 对于a∈R,令p=πpJi <$存在q∈ Lsuch使得p=u<$q且q−a→pJ使用线性转换,我们接下来定义封闭过程项的线性和复杂操作语义如下。p∈Lc的线性行为是(p)={u∈|p= 0}。R Rp∈ Lc对E的限制是p/E={u∈u|p= 0且E u=E}。p∈Lc的复定理为(p)={(p/Eu,Cons(p))|p=u}。[ACT]c−→cSKIP[SER1]p−a→pJp·q−a→pJ·q[REN]p−a→pJ[SER二、Cons(p)(τ)a,q−a→qJS(a)S(p)−τ→S(p)p·q−a→p·qJ[HID]p−a→pJ[PAR0个字符]a∈C,p-a→PJ,q-a→QJ的TTp(T\a)τp≤q−a→pJ≤qJCC[RES]p−a→pJ,a≤T[第1批]C,Cons(q)(τ)a,p−a→pJp<$T−→pJ<$(T−a)p≤q−a→pJ≤qτCτCrecx.p=q[REC][PAR]的一种C,Cons(p)(τ)a,q−a→qJ{x}p≤q−a→p≤qJq−τ→ p[q/x]CτC表1• 设p=0一2314D. Teodosiu/电子笔记理论计算机科学286(2012)307ø›→⊆Cø≤øø6指称语义接下来,我们使用复杂的多pomset环境上的函数域为我们的过程语言构建指称语义。我们赋予环境V的集合以乘积阶≤,即,我们设置(V,≤)=(,≤)V.缺点V:V →V 对于所有环境σ∈V, 且x∈V满足consV(σ)(x)= cons(σ(x)). 我们有一个典型的嵌入<$→,R(0,R),它允许识别它的形象在并设置。因此,任何关于V的函数都是关于V的函数。函数域是映射f:V→ 满足以下功能条件(i) 消费交换:cons(f(σ))=f(consV(σ))对于所有σ∈V,(ii) 消费连续性:f:(,≤)V→(,≤)连续,(iii) 复连续:f:(,≤)V→(,≤)是连续的。我们逐点提升排序≤from到也就是说,对于f,g∈我们定义f≤gi<$f(σ)≤g(σ),对所有的σ∈V.命题6.1通过替换封闭,并且(,≤)是DCPO。指称语义[[]]:L →下面归纳定义的是由指称唯一确定的,该指称将在接下来的小节中为每个无穷运算符符号定义为对具有相同的性质和满足功能条件 我们有[[],[]。T]], [[p<$T]],[[p·q]],[[p≤q]]∈ forp,q∈L)和将被定义为无穷递归算子符号作为对上的运算(也就是说,对于p∈ L,我们确实有[[recx.p]] ∈)。 因此,消费交换和连续性是直接检查,而复杂的连续性越来越难以证明。因此,从上述情况,我们可以预先说明以下几点定理6.2指称语义[[]]:L→归纳定义为[[SKIP]](σ)=(0, 0)[p·q]](σ)=[[p]](σ)·[[q]](σ)[[c]](σ)=(c,c)[p≤q]](σ)=[[p]](σ)≤[[q]](σ)C C[[S(p)]](σ)=S([[p]](σ))[x]](σ)=σ(x)[[p T]](σ)=[[p]](σ)T[[rec x.p]](σ)=(rec x.[[p]])(σ)[[p<$T]](σ)=[[p]](σ)<$T[10][11][12][13][14][15][16][17][17][18][19][19][1直接在操作器SKIP、c、S()、T、T_T、·和rec x的每个c h的表示上。 我们还将能够归纳检查以下内容C命题6.3如果p ∈ L,σ ∈V,则cons([[p]](σ))= Cons(p)(cons V(σ))。现在我们继续讨论我们语言的运算符的表示D. Teodosiu/电子笔记理论计算机科学286(2012)307315xT=(Re(x)T,cons(x)\T).øøøΣøø6.1重命名算子S(x)重命名相当于一个简单的重新标记,它保留了事件及其初始顺序。尽管它看起来很简单,但它允许在事件的标签上进行线性计算,因此可以用来从我们的语言中导出更多的运算符。对于每个S∈R,重命名算子S():,则定义为S([E,≤,ρ])=[E,≤,S(ρ)],其中对所有e∈E,S(ρ)(e)=S(ρ(e)). 对于每个S∈R重命名算子S():→对所有x∈定 义 为S(x)=(S(Re(x)),S(cons(x)。6.2隐藏操作符x Thiding操作符允许内部化某些给定的资源配额,并防止其他进程在使用它们的事件上进行同步。通常情况下,这表示需要本地,而不是全局,计算和通信。对于每一个T∈,隐藏算子T:→对所有[E,≤,ρ]定义∈通过[E,≤,ρ] T=[EJ,≤J,ρJ],其中(i) ρJ(e)=ρ(e)\(T\f<$eρJ(f)),(ii) EJ={e ∈ E |ρJ(e)/= 0},(iii) ≤ J= ≤ EJ×EJ。对于每个T∈隐藏算子T:→对于所有x∈,定义为:隐藏x T将给定的附加消费T从x的每个事件的过去中擦除,从而使其不可观察。6.3限制算子xT限制操作符在除了某些给定配额的资源之外的所有资源上阻止进程。例如,这是为了确保该进程在特定的安全环境中的保密性,并且可能在安全协议中有用对于每个T∈限制算子T:→对于所有x∈,定义为x∈ T ={y ∈|y≤x,cons(y)≤T}。 对于每一个T∈限制算子<$T:→对于所有的x∈通过x<$T=(Re(x)<$T,cons(x)<$T)。我们可以很容易地看到,x∈T是x对具有以下条件的事件集的限制:a在低于T的情况下消耗资源的过去,即,weexT=x/ExJ其中ExJ={e∈Ex|f≤xeρx(f)≤T}。6.4系列作品x· y下面的序列合成表示是[5]中处理串行组合强制第一个和第二个进程之间的同步,因此,第一个过程结束时的事件和第二个过程开始时的事件可能发生。316D. Teodosiu/电子笔记理论计算机科学286(2012)307.≤如果他们是独立的。这种构造可能在自动代码并行化和事务系统中有意义系列组成:2→对于所有的x1=[E1,≤1,ρ1]∈,x2=[E2,≤2,ρ2] ∈ 如果consinf(x1)≠ cons(x2)= 0 × x1·x2=[E,≤,ρ],其中(i)E=E1-E2,(ii)≤=(≤1)εstec{(e1,e2)∈E1×E2|ρ1(e1)<$ρ2(e2)/=0}临界温度(iii)ρ=ρ1<$stecρ2。≤2)≤ 1,系列组合物·:2→对于所有x,y∈,定义为x·y=(Re(x)·(Re(y)=Im(x)),cons(x)+cons(y))。它可以表明,使用串行组合与隐藏,使我们能够表示所有的紧凑的多pomset的封闭项的过程语言,这意味着指称语义是最佳的。6.5序贯合成x;y当需要两个过程在节奏上完全同步时,就应该采用顺序构图复合过程被安排成使得整个第一过程在整个第二过程之前发生,因此它们在时间上是有序的,即使是独立的。顺序组成;:2→ 设x1=[E1,≤1,ρ1]∈,x2=[E2,≤2,ρ2]∈byx1; x2=[E1<$stecE2,(≤1<$stecE1×E2<$stec≤2)<$,ρ1<$stecρ2]. 的顺序组成;:2→ 对于所有x,y∈,定义为:x;y=(Re(x); Re(y),cons(x)+ cons(y))如果Im(x)= 0(Re(x),cons(x)+cons(y))否则。可以证明,顺序合成可以表示为复合过程的重命名的序列合成,因此它是我们的过程语言的派生操作符。稍后我们将主要使用顺序复合来定义递归的指称语义。6.6平行组合x yC下面的平行合成是[4]中所处理的平行合成的推广。并行组合由一组通道索引,进程应该使用这些通道来同步。访问通道的事件通常由复合进程处理,而不使用通道的事件可以由每个复合进程独立处理。该构造可以特别地用于对在PRAM上运行的数据并行程序进行建模。设x1=[E1,≤1,ρ1],x2=[E2,≤2,ρ2] ∈是标准表示.我们定义了它们的pa l l lel位置yx1≤x2=[E1<$E2,(≤1 <$≤2)<$ ,ρ1 <$ρ2].注意,由于两个不同的原因,x1≤x2m可能不是实多点集。首先,≤可能不是反对称的。例如,如果x1=a;b且x2=b;a,则情况就是如此。其次,≤可能无法过同步。例如,如果x1=a,D. Teodosiu/电子笔记理论计算机科学286(2012)307317C且x2=b,其中<$(a<$b)。设x1,x2∈ 和CR。我们定义(r1,r2)∈C(x1,x2)<$2i <$(i) 对于所有i∈ {1, 2},我们有ri≤Re(xi),(ii) |R1|a=|R2|对于所有的a ∈ C,(iii) 对于所有{i,j}={1, 2}和a∈alph(ri),我们有a∈C或(a∈C和a∈xj),(iv) r1≤r2∈.平行组合物≤:2→ 对于所有的x1,x2∈ 和CRCbyx1≤x2=(r1≤r2,cons(x1)cons(x2))其中(r1,r2)=C(x1,x2).6.7递归运算符recx.f递归运算符的表示本质上不同于最小不动点语义。 实际上,递归运算符recx。:→,f<$→recx.f是通过使用两个链式不动点计算对所有f∈和σ∈V计算(recx.f)(σ)来定义的。首先,我们通过求解消耗域(,≤)中的递归来计算不动点的最小消耗,其次,我们通过求解复域(,≤)中的递归来计算具有最小消耗的最小不动点,如下所示。对于σ∈V,我们通常定义σ[x<$→y]在除x之外的所有参数上与σ相同,x被赋值为y 。对 于 x∈V , 我 们 定 义x :×V×→ 通 过 Cx ( f , σ , y ) ={x};f(σ[x<$→y]),和Ax:×V×→通过Ax(f,σ,R)={x}+ f(cons V(σ)[x <$→ R])= cons(Cx(f,σ,R)).首先,我们以R0= 0为下界,构造消费映射Ax(f,σ):(,≤)→(,≤),得到不动点x0(f,σ)=n ωRn(f,σ),其中Rn+1(f,σ)=Ax(f,σ,Rn(f,σ)),对所有n ω. 由于Ax(f,σ):(,≤)→( ,≤)是连续的,且R0是一个预动点,则序列Rn(f,σ)在DCPO中是递增的(,≤),因此最后一个上确界确实实存在。其次,我们以x0(f,σ)为下界,对复映射进行了构造(1)A(x,y)( ,≤)→( ,≤),它提供固定点(recx.f)(σ)=n ωxn(f,σ)其中xn+1(f,σ)= Cx(f,σ,xn(f,σ))对所有n< ω. 由于Cx(f,σ):(,≤)→(,≤)可以很容易地证明对每个x∈V和x0(f,σ)是一个预动点,则序列xn(f,σ)在DCPO(,≤)中是递增的,因此最后一个上确界确实存在。最后,我们证明了rec x。:→定义明确,即recx.f∈为所有f∈,而且rec x. :(,≤)→(,≤)是连续的。7全抽象与全抽象现在我们得到本文的主要结果,这些结果需要推广文[4]中提出的论点和结构。在这一节中,我们将陈述完全抽象的两个结果,一个是线性的,一个是复杂的。为此,我们首先318D. Teodosiu/电子笔记理论计算机科学286(2012)307ªRτ在运算侧的线性转换和指称侧的线性前缀和留数之间来回呈现线性转换下面的硬技术引理涉及算子与作用剩余的相互作用。请注意,表2的符号与表1的操作非常相似。对于所有的a∈R,x,xJ∈,如果a−1x=xJ,那么我们特别假设a x。引理7.1对任意a∈R<${0},x,xJ,y,yJ∈,c∈C,T∈,C<$R,f∈,σ∈V,我们有表2的性质。[ACT]c−1c()= 0a−1x=X[SER[1]a−1x=xJa−1(x·y)=xJ·ycons(x)a,a−1y=yJ[REN][HID]S(a)−1S(x)=S(xJ)a−1x=X(a\T)−1(x<$T)=xJ<$(T\a)[SER2][PAR0个字符]a−1(x·y)=x·yJa∈C,a−1x=xJ,a−1y=yJa−1(x≤y)=xJ≤yJCC[RES]a−1x=xJ,a≤Ta−1(x<$T)=xJ<$(T−a)[第1批]C,cons(y)a,a−1x=xJa−1(x≤y)=xJ≤y C C[REC](recx.f)(σ)=y{x}−1y=f(σ[x<$→y])[第2批]C,cons(x)<$a,a−1y=yJa−1(x≤y)=x≤yJC C表2下一个命题,很容易证明依靠命题6.3和前面的引理,允许我们将线性转移的操作侧的符号侧的线性剩余。对于所有的u∈n,x,xJ∈如果u−1x=xJ,则我们特别假设u x。R命题7.2设u∈N,p,PJ∈ L,σ∈V,τ=cons V(σ). 然后p=u<$pJ=<$u−1[[p]](σ)=[[pJ]](σ)下面简单的技术引理涉及操作符与动作前缀的交互。引理7.3对任意a∈R,x,y∈,c∈C,T∈,C<$R,f∈,σ∈V我们具有表3的性质。下一个命题很难依靠命题6.3和前面的引理来证明,它允许我们将指称侧的线性前缀转换为运算侧的线性转移。主要的困难在于充分处理隐藏算子,这是最困难的情况。我们只获得了一个我们称之为nice的不包含隐藏的术语的大子类D. Teodosiu/电子笔记理论计算机科学286(2012)307319ªªªª ªªªøR<$[[p]](τ)=p=R[REN] a<$S(x)=<$b<$x,对于某个b∈R,使得a=S(b).[PAR]a<$x≤y=n(a∈C且a<$x和a<$y)或RRRR[ACT]ac = a =c.[HID]a<$x<$T=<$u<$ub<$x,对于某些u∈<$且b∈R使得uRT= 0且(ub)T=a[RES]ax<$T =<$ax且a≤ T。[SER]ax·y =<$(a x)或(cons(x)<$a and ay)。(C,cons(y)a和a_x)或(C,cons(x)a and a y).[REC] a <$(rec x.f)(σ)= σ a ={x}。表3隐藏开放子项变量的项,对于任何实际目的,假设这种条件都是相当合理的。令≤表示L中的子项序。p∈L是一个好项i ∈ P,对于所有子项p1T≤p,则T∈V= 0或p1∈Lc. 好项的集合由Ln表示, 用Lc,n表示良好且封闭的项的集合。命题7.4设u∈Ln,p∈Ln,τ∈V. 然后乌乌τ使用线性平移,我们能够陈述线性行为的指称表征,其仅观察动作串定理7.5(线性同余)对所有p∈ Lc,n,我们有(p)={u ∈ |[[p]]}作为一个主要的结果,我们接下来推断出一个线性的完整的抽象探测过程中合适的隐藏上下文。一个上下文C()是一个C∈ L的项,其中一个区别变量记为.一个上下文C()是好保持的i <$C(p)∈ Ln,只要p∈ Lc,n.定理7.6(线性全抽象)对于所有p,q∈ Lc,n,我们有[[p]] = [[q]]对于所有的保良C(),我们有(C(p))=C(q)利用每个多pomsetx∈是它的线性化集Lin(x)的交集这一事实,我们导出了复杂行为的指称特征,它观察到多pomset的动作。C320D. Teodosiu/电子笔记理论计算机科学286(2012)307R定理7.7(复同余)对所有p∈ Lc,n,我们有(p)=Kmp([p]])和[[p]]=(p)这允许我们最终推断出复杂的完全抽象结果。定理7.8(复全抽象)对于所有p,q∈ Lc,n,我们有[[p]] = [[q]]对于所有的保良C(),我们有(C(p))=(C(q))最后,我们的演示文稿与结果有关的指称语义的双相似性和消费语义。一个关系S <$Lc,n× Lc,n是互模拟i <$,对所有u ∈<$ 我们有• p Sq和q=u<$qJ那么p=u<$pJ和pJSqJ对于某个pJ,• p Sq和p=u<$pJ那么q=u<$qJ和pJSqJ对于某个qJ。粗糙互模拟|S互模拟},称为双相似性,已知是等价关系(例如参见[8])。定理7.9对所有p,q∈ Lc,n,我们有[[p]]=[[q]] Cons(p)= Cons(q)and p q.8结论我们开发了一个真正的并发语义,允许描述递归进程访问消耗资源的并发行为。首先给出了实复集的相干完备和素代数基域。模型化的过程语言包含几个确定性的定量过程操作符以及一个递归操作符。接下来,我们展示了一个确定性的结构操作机器,它很容易理解,并允许提取线性和复杂的行为。然后,我们构建了一个复合指称语义使用功能域的复杂的多pomsets的环境。主要结果最终表明,指称语义是完全抽象的线性和复杂的操作语义。在经典过程语言[7,8]中,唯一一个被我们有意忽略的操作符是非确定性选择。我们认为在复杂的多pomset上使用幂域提供了一种处理选择的清晰方法实现相同结果的另一种可能性可以在于丰富真实的多pomsets,其中具有关于表达选择冲突的事件的进一步关系,从而施加更接近事件结构的建模视图。除了在工程和经济中的预期应用外,所提出的语言还可以作为一种强大的形式主义来抽象地指定和D. Teodosiu/电子笔记理论计算机科学286(2012)307321处理标记的偏序,这些偏序比文献中通常考虑的串并联结构复杂得多。确认我感谢Paul Gastin进行了几次富有成效的讨论,感谢Volker Diekert指出了有趣的扩展,感谢Daniele Varacca 提出了建设性的批评,感谢Pierre-LouisCurien提出了各种中肯的意见。引用[1] S. Abramsky,A.郑域理论在Handook of Logic in Computer Science,Vol. III,pages 1-168,ClarendonPress,1994中。[2] V. Diekert,P. Gastin.并发终止域:Mazurkiewicz迹的推广。1995年,第22届自动机、语言和程序设计国际学术讨论会论文集。计算机科学讲义944,第15-26页,Springer,1995年。[3] M. Droste , W. Kuich , H. 沃格 勒加权 自动机 手册。EATCS Monographs in Theoretical ComputerScience,Springer,2009.[4] P. Gastin,M.失恋。一个真正的并发语义的进程代数使用资源Pomsets。理论计算机科学,第281卷,第1-2期,第369-421页,2002年。[5] P. Gastin,D.特奥多休资源跟踪:进程共享独占资源的域。1996年,第十二届编程语义学数学基础。Theoretical Computer Science,第278卷,第1-2期,第195[6] M. Hennessy,G. D.普洛特金一个简单的并行编程语言的完全抽象。 计算机科学讲义74,Springer,1979。[7] C. A. R.霍尔通信顺序进程。Prentice-Hall International Series in Computer Science,Prentice Hall,1985年。[8] R.米尔纳通信和并发。Prentice Hall International Series in Computer Science,Prentice Hall,1989。[9] 普拉特。使用偏序的并发建模。International Journal of Parallel Programming,第15卷,第1期,第33-71页,Kluwer Academic Publishers,1986年2月[10] D.皮姆角托夫特资源和过程的演算和逻辑。Formal Aspects of Computing,第18卷,第495-517页,2006年。[11] D.特奥多休一个共享量化资源的进程的真正并发语义。 巴黎第七大学计算机科学系博士论文,2012年3月,见http://teodosiu.pagesperso-orange. fr。[12] G.温斯克事件结构。In W. Brauer,W. Reisig,G. Rozenberg(编辑),Petri Nets:Applications andRelationships to Other Models of Concurrency,Advances in Petri Nets 1986,Part II; Proceedings of anAdvanced Course,Bad Honnef,September 1986,Lecture Notes in Computer Science255,pages 325-392,Springer,1987
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 十种常见电感线圈电感量计算公式详解
- 军用车辆:CAN总线的集成与优势
- CAN总线在汽车智能换档系统中的作用与实现
- CAN总线数据超载问题及解决策略
- 汽车车身系统CAN总线设计与应用
- SAP企业需求深度剖析:财务会计与供应链的关键流程与改进策略
- CAN总线在发动机电控系统中的通信设计实践
- Spring与iBATIS整合:快速开发与比较分析
- CAN总线驱动的整车管理系统硬件设计详解
- CAN总线通讯智能节点设计与实现
- DSP实现电动汽车CAN总线通讯技术
- CAN协议网关设计:自动位速率检测与互连
- Xcode免证书调试iPad程序开发指南
- 分布式数据库查询优化算法探讨
- Win7安装VC++6.0完全指南:解决兼容性与Office冲突
- MFC实现学生信息管理系统:登录与数据库操作
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功