没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记128(2005)103-122www.elsevier.com/locate/entcsEsterel的确定性逻辑语义Olivier Tardieu1INRIA,Sophia Antipolis,法国摘要Esterel是一种用于反应式系统规范的同步设计语言。 有两个主要的语义Esterel。一方面,逻辑行为语义提供了一个简单而紧凑的形式化的行为的程序使用SOS规则。但它并不能确保所有程序和所有输入的确定性执行。 由于非确定性程序必须被拒绝为不正确的,这意味着它定义了不正确程序的行为,这是不方便的。另一方面,构造性语义是确定性的(在其他属性中),但代价是更复杂的形式主义。 在这项工作中,我们构建并彻底分析了一个新的确定性语义Esterel,保留了简单的逻辑行为语义,从它派生。在我们看来,它提供了一个更好的框架,正式推理的Esterel程序。保留字:同步语言,并发理论,结构操作语义。1介绍Esterel [7,8]是一种高级命令式并行编程语言,用于指定反应式系统[9,13]。它诞生于八十年代[6],并从那时起不断发展。在这项工作中,我们考虑Esterel v5方言[4,5]由当前的学术编译器[1,10]认可。纯Esterel是完整Esterel语言的子集,其中数据变量和数据处理原语被抽象掉。由于我们在这项工作中感兴趣的问题与数据无关,我们将专注于纯Esterel语言。Esterel是一种同步语言[2]。除了一个暂停指令外,原语构造的执行时间为零。因此,时间序列是一个对数序列,1电子邮件:olivier. sophia.inria.fr1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2004.09.040104O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103由明确的停顿分隔的典型瞬间。在每个瞬间,几个基本的瞬时计算同时发生。艾丝特瑞尔处理信号。信号具有布尔状态,它遵循信号相干定律:在每个瞬间,信号默认为不存在,如果在该瞬间发出,则存在。例如,在“present Athen emit B end“中缺席和在场都是即时广播的,并且同时可用于所有执行线程。这种完美的同步假设可能导致因果循环[4,14],例如在平行组合中呈现A然后发射B结束||当前B然后发射A结束其允许符合信号相干定律的两种可能的执行• A和B都存在并发射;• A和B都不存在并且不发射。这个程序被认为是不确定的。类似地,存在不可能执行的非反应程序,例如:呈现A然后发射B结束||present B else emit A end在Esterel中,我们希望程序具有无死锁的确定性执行。因此,非反应性和非确定性程序必须被视为不正确而拒绝。已经为Esterel形式化了两个主要语义• 逻辑行为语义学[3]简单地形式化了信号相干律。它定义了一个非反应性程序没有执行,而一个非确定性程序有几个不同的执行。• 构造性语义学[4]的灵感来自于数字电路和三值逻辑.它只定义了由逻辑行为语义定义的执行的子集。通过拒绝更多因此,它定义了不执行非反应性和非确定性程序。这两种语义以相反的方式处理非确定性也不是真的方便。• 一方面,由逻辑行为语义定义的执行不一定是正确的,因为它可能是一个不确定的执行,因此是不正确的程序。此外,非确定性有时会补偿非反应性,使程序具有反应性和确定性,尽管它包含非反应性或非确定性的代码片段[2]一般来说,决定论和反应性取决于输入。第4节)。O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103105• 另一方面,构造性语义学只定义了正确的表达式,但代价是复杂得多的形式主义。因此,我们在这项工作中引入第三种替代语义,我们从逻辑行为语义。它保留了逻辑行为语义的简单形式,同时只定义正确的执行。特别是,它确保错误不会相互抵消。本文件的结构如下。在第2节中,我们描述了纯Esterel语言。我们在第3节中形式化了它的逻辑行为语义,并在第4节中讨论了反应性和决定性。我们在第5节中建立了确定性语义。在第6节中,我们彻底比较了这两种语义。我们在第七节中简要讨论了Esterel的构造语义,并在第八节中进行了总结。2语义学与直觉语义学p,q::=nothing什么都不做,立即暂停停止执行,直到下一个瞬间p;q运行p,则q如果/当p终止时p||q使p与q并行循环p结束永远重复p信号Sinpend声明信号SinpemitS发射信号SpresentSthenpelseqendrunp ifS is present,qotherwisetrapTinpend声明,捕获异常TinpexitTd引发深度为d的异常TFig. 1. 原始纯Esterel构造在不失一般性的情况下,我们将重点放在Berry [4]启发的内核语言上,它保留了足够的纯Esterel语言以实现其完整的表达能力。图1描述了我们的内核语言的语法,以及它的构造的直观行为非终结符p和q表示语句(即程序)、S信号和T异常。信号和异常都是标识符,它们在词法上是有作用域的,并分别在语句中通过构造infix“;“运算符绑定得比“||“. 方括号“[“和“]“可用于以任意方式对语句进行分组。 在当前语句中,then或else分支可以省略。例如,106O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)1032.1瞬间和反应Esterel语句以称为反应的步骤运行,以响应全局时钟的滴答声。每个反应都需要一个瞬间。除了暂停指令外,基本构造在零时间内执行。当时钟滴答作响时,会发生反应,根据输入信号和程序的当前状态计算输出信号和程序的新状态它可能会立即完成执行,也可能会延迟部分执行到下一个时刻,因为它至少到达了一个暂停指令。在后一种情况下,当时钟再次从前一时刻到达的暂停指令的位置滴答作响时,等“ 它需要三个瞬间完成,也就是说,通过三个反应进行。 信号B和C是同时发出的,因为它们的发射发生在执行的同一时刻。特别是,2.2同步并发Esterel中的并发是同步的。平行组合物“p”的一个反应||q“由每个未终止分支的恰好一个反应组成,直到所有分支终止。比如说,[暂停;发出A;暂停;发出B||发出C;暂停;发出D];发射E在执行的第一个瞬间发出C,然后在第二个瞬间发出A和D,然后发出B和E,并在第三个瞬间终止。2.3例外它们是词法作用域,由“trap T in p end“构造声明和捕获整数d编码“退出T“的深度• 如果O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103107• 如果比如说,陷阱T在陷阱U在因为声明了U,所以退出T1 的深度为1||出口U0的深度为0||出口V3可以具有大于或等于2的任何深度结束;出口T0的深度为端这种对Esterel异常的像往常一样,我们将只在必要时才使深度显式化在顺序代码中,exit语句的行为就像一个比如说,陷T于发出A;暂停;发出B;退出T;发出C结束;发射D在第一个瞬间发射A,然后是B和D,并在第二个瞬间终止信号C从未发出。在并行上下文中引发的异常会导致所有并行分支立即终止。在下面的例子中,A和E在第一个瞬间发射,然后B,F和D在第二个和最后一个。C和G都不发射。陷T于发出A;暂停;发出B;退出T;发出C||发射E;暂停;发射F;暂停;发射Gend;emit D备注异常实现弱抢占:异常声明可以嵌套。在下面的例子中,A没有被发出,因为最外面的异常T优先于内部的异常U。108O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103陷阱T在陷阱U在T1出口||退出U 0结束;发射A端换句话说,深度更大的例外总是优先的。2.4环语句通过组合loop、trap和exit语句,可以获得完全迭代的循环,例如在“await S“的内核扩展中在循环暂停中捕获T;呈现S然后退出T end end end循环体可能不是瞬时的[17]。例如,这样的模式将阻止反应达到完全。因此,循环体需要引发异常或将控制保留至少一个瞬间,也就是说,在每次迭代中执行暂停或退出2.5信号指令 语句的自由信号被称为该语句的接口信号。在一个瞬间,如果在该瞬间执行至少一个“emit S“语句,则发出信号S在瞬间,信号S的状态是存在或不存在。如果S存在,则在该时刻执行的所有否则,它们都执行它们的• 本地信号在其被发射时存在• 如果环境提供接口信号,则存在接口信号。备注:接口信号可能不存在,也可能发出。比如说,• 在“信号S在发射S;暂停;呈现S然后发射O结束结束“中,S只在执行的第一个瞬间出现,因此O不会被这个语句发出,因为S在“present S“测试时不存在• 在“信号S在当前S然后发射O结束||emit S end“,两个SO是发射的,S是存在的。• 在“emit X; present X then emit O end“中O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103109哦,k⎧⎨04I环境,因此O是由环境提供的。3逻辑行为语义学Esterel [4,11]的逻辑行为语义将前一节的非正式它描述了一个语句p通过一个标记的转移系统的反应:p−−I→pJ其中:• 集合I是当前信号的集合,• 集合O是发射信号的集合,• 整数k是反应的完成,• 陈述PJ是反应的残余物。图2将Esterel的逻辑行为语义表示为结构化操作风格中的一组事实和演绎规则[16]。3.1完成代码和剩余完成码k和残差pJ编码执行的状态:• 如果k= 1,则该反应不完成p的执行。它必须在下一个瞬间通过执行pJ来继续• 如果kj= 1,则该反应结束p的执行(pJ无关紧要):· k= 0,如果执行正常完成(无异常)。· k=d+2,如果深度为d的异常从p逃逸。特别地,“exit T d“的完成码为了从p的完备化k计算“trap T in p end“的完备化码↓k=0如果k= 0或k= 21如果k= 1如果k >2,则为k−1方便地,如果p以完成码k终止,q以完成码l终止,则“p||q“以代码“max(k,l)"终止。比如说,trapTinexitT||exitVend−∅−→,3无底110O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103−−→−−→emitS{}emit S{}−−→−−→−−→−−→I−−→1...On,kn最终执行:p−−→Ip−−→In3.2存在和发射信号箭头下方的集合I列出了环境提供的信号。它推动了本声明的反应:哦,k• 如果S∈I且p−−I→哦,k• 如果S∈/I且q−−I→pJthenpresentSthenpelseqendO,k我qJ则存在S则pelseqendO,k我pJ。qJ.写在箭头上方的集合O列出了发出的接口信号。特别是,S,0--我--没什么信号相干性定律-本地信号在发射后存在(信号+)如果假设S存在于p中,则它由p发射;(信号-)如果假设S不存在于p中,则它不是由p发射。例如,对于输入I={A},S ,0−{−A−,S→}无S∈{S}信号S在发射器S端,0{A} 信号S无结尾使用(信号+)暂停,1{A} 无S∈/ε使用(信号−)暂停结束时信号S,1{A} 信号S无结尾我们稍后将进一步讨论这些规则。3.3执行语句p的执行是一个潜在的无限反应链,使得所有的完成码都等于1,但最后一个在有限情况下:O0,1• 有限执行:p0pO1,11−−I−→pn+1,其中hk=1,对于somen∈N.O0,1·0O1,11I1... −O−n−→,1.我们说I =(I0,I1,...,I n)和I =(I n)n∈N是执行的输入序列。类似地,O是输出的序列。O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103111−−→−−→∅emitS{}−−→p||q−−−→哦,k−→q−−−−−−→−−−→没有什么,0我Nothing(无)暂停,1我无(暂停)出口T,d+2d−−I−→nothingg(exit)S,0−I−→nothingg(emit)哦,kpIp哦,k循环p结束k=0pJ;looppend(循环)哦,kp−−I→J哦,我J−−I→pq−−I−→q(平行)O O',max(k,l)−−I−→p|| qJ哦,kS∈Ip−−I→p(present+)哦,k呈现Sn个像素eqend−−I→p哦,kS∈/Iq−−I→q哦,k(present−)表示S的n个像素eqend−−I→qJO,2p−−I→p(trap-catch)O,0trapTinpend−−I→无哦,kp−−I→pk/= 2(Trap-through)p端O中的陷阱T,↓k我pJ端的陷阱Tp−−I→ pJk/= 0哦,k(序列-p)p;q−−I→pJ;qO,0p−−I→p哦,k−−I−→q(序列-q)p;qO≠O', kJ我哦,kp−I−S−{−S→}pS∈O信号SinpendO\{S},k 信号SinpJend(信号+)我哦,kp−I−\−{−S→}pS∈/O哦,ksignalSinpend−−I→信号SinpJend(信号−)图二. 逻辑行为语义学例如,语句在执行的第二和最后时刻,B被发出。发出A;暂停;发出B{A},1I0nothing;QJJJJJJJJJJJ112O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103−−−→emit B{B},0I1没有什么O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103113−−→I{A}−−→−−→−{−−→A,S}−−−→−−→−−→I−−→I反作用证明没 有 什 么1循环无结束0信号S在当前S中否则发射S结束结束 0信号S在当前S中然后发射S结束结束 110022我们记p → PJi,则存在I和O使得pO,1 PJ。我们说q是可从pi p→piq获得,其中r→p i q是pip→ p iq的关系式。4逻辑正确性根据语句p和输入I,逻辑行为语义可以定义零个、一个或多个反应。此外,一个给定的反应可能有一个以上的证明,也就是说,由一个以上的组合物产生语义学的规则例如,对于I={A},特别是,对于S∈/{A}nothingg−−,→0没有什么present S then emit Send{A} 无S∈/ε在当前S中的信号S然后发射S结束结束,0{A} 信号S无结尾S∈{A,S}emitS{S},0没有什么presentSthenemitSend{S},0{A,S} 无S ∈{S}在当前S中的信号S然后发射S结束结束,0{A} 信号S无结尾“信号S在存在S中然后发射S结束结束“的内部行为然而,观察到的行为是确定性的。我们期望程序具有确定性的无死锁执行。因此,我们必须丢弃没有或有太多可能行为的“不正确”程序。在本节中,我们形式化这样的正确性标准。我们定义:• p是反应的i,对于所有的I,至少存在一个元组(O,k,pJ)s. t。 pO,k• p是确定性的i??对于所有I,至多存在一个元组(O,k,pJ)s. t。 pO,kpJ。pJ。114O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103−−−−−→• p是强确定性的,且对于所有(I,O,k,pJ),哦,kprooofofp−−I→pJ是唯一的,如果它存在。• p是逻辑正确的,如果对于从p可达的所有q,q是反应性的和决定性的。• p是强正确的,且对于所有从p可达的q,q是反应性的和强确定性的。确定性确保语句的观察行为是确定的。强决定论保证了它的内部行为也是决定性的。反应性与(强)决定论相结合,确保了无论输入如何,对于这个陈述都存在唯一的反应(具有唯一的证明)。逻辑正确性的特征是语句对任何输入序列都具有确定性的无死锁执行此外,强正确性确保了强确定性。一旦必须考虑到副作用或调试,强正确性就成为一个问题,因为两者都可能暴露程序的内部行为。当然,强正确性意味着逻辑正确性。5确定性语义逻辑行为语义提供了一个非常紧凑的,结构化的形式化的行为的Esterel程序,这使得形式化推理的语言易于处理。此外,它定义了反应性和决定性,这是Esterel程序的最低正确性标准。然而,使用这些标准可能是乏味的。虽然反应性可以用简单的证明树来证明,但建立(强)确定性更复杂,并且形式上需要关于证明树的证明(唯一性证明)。此外,首先为非(强)确定性陈述定义许多(证明)反应,然后我们丢弃这些反应,因为它们太多了,似乎完全不明智。因此,我们建议重写本地信号声明的规则:p−−O−,k→pJS∈O我来{S}信号SinpendO\{S},k我信号SinpJ end(信号+)哦,kp−I−\{−S→} pJS∈/O(信号−)哦,ksignalSinpend−−I→信号SinpJendO. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103115ıO\{S},kp O,kı−−−−→−−−→−−→O、k+随着流动(w,这里k+,k-,etc. 除了名字以外什么都没有):O−,k−−−I\−{−S→}pS∈O−O+、K+p−I−ε−{−S→}pS∈O+(信号++)++signalSinpend−I−−→signa lSinp端-−−−I\−{−S→} pS∈/O−++p−I−ε−{−S→}pS∈/O+信号S在p端为<$O−,k−信号Sinp−end我(信号−−)我们把结果语义称为确定性语义,并用转换符号“›→"表示相应的反应。直觉上,它包括在每个信号规则中强制执行另一个不适用的规则,而不引入否定前提[12],例如:S,p,I,O,k和pJ不使得pO,k我来{S}pJ和S∈O而不是否定整个前提条件,我们只交换二元决策对于S∈/O,S ∈ O,并且viceversa。在逻辑分析中,我们有:• (信号+):如果假设S存在于p中,则它由p发射。• (信号−):如果假设S在p中不存在,则它不是由p发射的。在我们的确定性语义中,信号构造的规则变为:• (信号++):· 如果假设S存在于p中,则它被发射。· 如果假设p中不存在S,则它仍然被发射。• (信号−−):· 如果假设S在p中不存在,则它不被发射。· 如果假设S存在于p中,则它也不被发射。5.1示例例如,在以下两种情况下,确定性语义产生与逻辑行为语义相同的反应(参见:第3节):pause暂停,1第1−{−A→} 无g S∈/pause−{−A−,S→} 无S∈/ε暂停结束时的信号S,1{A} 信号S无结尾p−++−116O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103−−→−−→我−−→I−−→IemitS{S},0{S},0−−{A−}→nothingg S∈{S}emitS−{−A−,S→}nothingg S∈{S}信号S在发射器S端发射,0{A} 信号S无结尾确定性语义学定义了对以下情况没有反应:• 非反应性声明:“• 非确定性声明:“• 非强确定性声明:“5.2决定论新的语义是全局确定性的:定理5.1对所有p和I,至多存在一个(O,k,pJ)s. t。pO,k我pJ。Theorem5. 2对于lp,I,O,k,pJ,p ∈O−,→kpJ是唯一的,如果它存在。证据简单的结构归纳法。Q在确定性语义学中没有必要计算证明和反应5.3正当性由于证明和反应的唯一性得到了保证,我们可以说,关于确定性语义,即,陈述p是正确的。适当地,确定性语义定义了对于任何输入序列,在p的执行的任何阶段至少有一个反应。形式上,我们定义:• p初始真i ≠对所有I,存在(O,k,pJ)使得p≠O,kpJ。• p<$→pJi <$存在I和O使得p<$O,1pJ。• →∗ 是<$→的自反传递闭包。• p是properi n,对于所有q,q,q是初始值。6比较我们现在精确地将逻辑行为语义和确定性语义联系起来O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103117ı−−→ı−−→ı−I−\{−→S}−−−→我−−6.1适当性意味着强正确性哦,kTheorem6. 1如果p−−I→pJ那么pO,k我pJ。定理6.2若p≠00,k0PJ和pO1,k1pJ然后O=O,k= k,PJ= PJ.−−I−→0−−I−→10 1010 1哦,kTheorem6. 3如果p−−I→那么证明pO,k我p是唯一的。证据 参见附录A.Q通过编写哦,kp−−I→p我们不仅在确定性语义中表示p可以对输入I作出反应,输出O、完成码k和残差pJ,因此在逻辑行为语义中也是如此(Th.6.1),但它也必须以这种方式反应,两种语义(Th.5.1和6.2),其内部行为是确定性的(Th。5.2和6.3)。因此,推论6.4如果p是真的,那么p是强正确的。6.2强正确性并不意味着适当性反过来,一个强正确的陈述不一定是适当的,因为与强决定论相结合的反应性并不意味着初始的适当性。让• 信号spresent S then loop nothing end endend对于所有输入I,逻辑行为语义定义了这个程序的以下S∈/I\{S}nothingg没有什么present S then loop nothing endend0I\{S} 无S∈/εSignalSinpresentSthen. endend−−,→0信号S无结尾然而,确定性语义学没有定义对这个陈述的反应,无论I。 既不是规则(信号++),也不是规则(信号 )适用,因为J118O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103−−→−−→• 回路信号spresent S then emit S else pause endend端主体在逻辑行为语义中,无论I是什么,循环都可以以两种可能的方式进行反应,并具有相应的完成码0和1:信号S在当前S中则发射S,否则暂停结束结束,0我信号S在当前S中则发射S,否则暂停结束,1我......由于这两个反应中只有一个允许非零完成码,所以整个循环语句既是反应性的,又是强确定性的。另一方面,确定性语义定义了主体没有反应,因此循环也没有反应6.3强烈纠正不恰当的陈述在逻辑行为语义中,非确定性可以补偿非反应性,或者相反,使得一段不正确的代码可以嵌入到强正确的程序中。更准确地说,定理6.5如果p是反应的和强确定的,但不是初始真的,则存在p的子项q,使得q不是反应的或不是强确定的。证据 参见附录B.Q直觉上,q在p中表现良好只是因为它的出现上下文,它从外部约束q的执行,确保q的非反应性或非强确定性行为永远不会被触发。换句话说,q可以被简化,同时保持p的行为。让• 信号spresent S then loop nothing end endend子项因此,它可以被它的隐式else分支所取代,也就是说什么都没有,导致O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103119相当于3个程序“信号S在没有结束”,这是正确的• 回路信号spresent S then emit S else pause endend端主体不是确定性的,但是封闭循环强制S不存在。同样,由此产生的程序因此,这些程序有问题,即使逻辑正确性和强正确性对它都不敏感。无论如何,它们是没有实际目的的复杂结构7建构语义学Esterel [4]的构造性语义确保了行为可以有效地计算,也就是说因果地计算。例如,尽管下面的程序在逻辑上是正确的,甚至强正确的,因为S只能存在,但它被构造性语义拒绝:信号S在当前S中则发射S,否则发射S结束结束直觉上,这个程序不是建设性的,因为S的状态必须在它发射之前被“猜测”。然而,这样的论点与确定性语义无关,它认为这个程序是正确的。另一方面,确定性语义学有时会拒绝重复性程序,例如:信号S在当前S中,则信号T当前T否则发射T结束端由于S不能被发出--没有"emit S"语句--当前语句的then分支永远不会被构造性语义"访问"。因此,该方案具有建设性。另一方面,确定性语义确实探索了这个分支,因此程序是不适当的。3从技术上讲,它们是强双相似的[15] w.r.t.逻辑行为语义学。120O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103哦,k哦,kO0,k 0哦,k−−我−−0000构造性语义中的执行由(复杂的)单调信息传播过程定义,每个程序和每组输入最多定义一个反应。换句话说,在第5节的意义上,语义是全局确定性的。总之,即使两种语义都是全局确定性的,这种属性的原因也是非常不同的,并且相应的正确性标准是不相关的。两者都有意义,可以结合起来。8结论与Esterel的逻辑行为语义相反,我们在这项工作中引入的确定性语义定义了所有程序和所有输入的最多一次执行。特别是,如果确定性语义定义了程序的执行,那么这个执行是唯一的,因此是正确的。重要的是,确定性语义不会改变“合理”程序的语义。如果一个程序的确定性语义被定义,那么它就与它的逻辑行为语义相匹配。反过来,如果程序的确定性语义没有定义,那么程序或程序的某些子项是不正确的。逻辑行为语义学。此外,我们的新语义实现确定性的成本比Berry的建设性语义低得多。因此,我们认为,决定语义提供了一个更好的起点,形式化推理的Esterel程序比逻辑行为语义和建设性语义。A定理6.1 ~ 6.3通过对p的结构归纳,我们可以证明,如果p<$−−I→pJ则:• p−−I→ pJ有唯一的证明;• 如果p−−→ pJ则O = O,k = k,pJ= pJ.证据 让我们考虑p =“q端的信号S“的情况,并选择一个集合I。通过假设,存在(O,k,pJ)使得:信号Sinqend−I→pJ必须使用(signal++)或(signal)规则来定义这种反应。让情况(信号++)类似。存在ts(O−,k−,q−,O+,k+,q+)sucht:O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103121ıııı0000q=O,kıO、k+O−,k−• q−−I\−{−S→} QO+、K+且q−I−ε−{−S→}Q• S∈/O−, S∈/O+, O= O−, k= k−,pJ=“signa l S i n q − en d“。因此,以下推论在确定性语义中成立:O−,k−−−I\−{−S→}QS∈/O−O+、K+q−I−S−{−S→}QS∈/O哦,kp=signalSinqend−−I→q−end中的信号S=pJ通过归纳假设:O−,k−• q−−I\−{−S→}q-有唯一的证明。O0−,k0−• 如果qq−则O−= O−,k−= k−,q−= q−。−−I\−{−S→}0O+、K+ +0 0 0• q−−I<$−{−S→} QO+、K+• 如果q−→一个独特的证据。q+ n O+=O+,k+=k+,q+=q+.0我来{S}0 0 0另一方面,当S∈/O+时,对于p的n或eα可以使用(signal+)来确定。另一方面,根据规则(信号-),O−,k−• p−I−→信号S在q−end中具有唯一的证明。哦,k• 如果p−−I−→pJ0 然后O0 =O−,k0=k−,pJ0=q−end中的信号S。对于所有其他情况也是如此。QB定理6.5通过对p的结构归纳,证明了如果p及其所有子项是反应的且强确定的,则p是初始真的.证据让我们考虑p =“q端的信号S“的情况,并选择一个集合I。通过假设,q及其所有子项是反应性的和强确定性的。通过归纳假设,q最初是真的。因此,存在(k−,O−,q−,k+,O+,q+)su cht hat:有四种情况:-−−−I\−{−S→}Q++且q−I−ε−{−S→}Qq−+−++−122O. Tardieu/Electronic Notes in Theoretical Computer Science 128(2005)103−−−−−−−→−→I∈ ∈−by规则(信号+),p−I−−→信号Sinq• S∈O−,S∈O+ ,n由yrule(signal++),p∈O+\{S},k+信号Sinq+我端• S∈/O−,S∈/O+,thenbyrule(signal−−),p<$O−, k−q−end中的信号S。• S∈O+,S∈/O−:·O+\{S},k++O−,k−·by规则(signal−),p−−I−→ q−end中的信号S因此,p不是强决定性的。矛盾• S/O+,SO-,当n或(s信号+)n或(s信号)是可应用的。因此,p不是反应性的。矛盾类似地,在所有其他情况下,确定性语义定义了对p,无论我。 因此,p最初是适当的。Q引用[1] Esterel v5 92发动机,http://www-sop.inria.fr/esterel.org/。[2] Benveniste,A.,P. Caspi,S. Edwards,N. Halbwachs,P. Le Guernic和R. de Simone,TheSynchronous Languages Twelve Years Later,Proceedings of the IEEE 91(2003),pp.64-83.[3] Berry,G.,纯Esterel的语义,在:M。Broy,editor,Program Design Calculi,SeriesF:Computer and System Sciences118(1993),pp.361-409[4] 贝瑞G.,的建设性语义的纯艾斯特瑞尔草案版本3(1999年),http://www-sop.inria.fr/esterel.org/.[5] Berry,G.,EsterelV5语言入门。第591版(2000年),http://www-sop.inria.fr/esterel.org/.[6] Berry,G.和L. Cosserat,同步编程语言Esterel及其数学语义,LNCS 197(1984),pp. 389-448.[7] Berry,G.和G.Gonthier,The Esterel synchronous programming language:Design,semantics,implementation,Science of Computer Programming19(1992)。87比152[8] 布西诺湾和R. de Simone,The Esterel language,Another Look at Real Time Programming,Proceedings of the IEEE79(1991),pp. 公元1293-1304年。[9] 爱德华兹,S.,[10] Edwards,S.一、Kapadia和M. Halas,Compiling Esterel into Static Discrete-Event Code,in:Synchronous Languages Applications and Programming,2004.[11] 再高一点,吉。,“S'ema n ti que e t mo d ` ele s d ' e x' ecut io n d e s la ngage s r 'eac t if s y n cron es:a p p lica t ion a ` Es terel,“T h ` es e d 'i n forma t i que e,U i v e rsit 'e d ' O rs ay y,Paris,F ra n c e(1988).[12] Groote,J.F.,具有负前提的过渡系统规范,在:CONCUR332-341。[13] Halbwachs,N.,[14] Malik,S.,循环组合电路的分析,在:IEEE/ACM国际CAD会议,ACM/IEEE(1993),pp.618-627端
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 李兴华Java基础教程:从入门到精通
- U盘与硬盘启动安装教程:从菜鸟到专家
- C++面试宝典:动态内存管理与继承解析
- C++ STL源码深度解析:专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手:数据管理与企业增值的战略
- Eclipse IDE基础教程:从入门到精通
- Shell脚本专家宝典:全面学习与资源指南
- Tomcat安装指南:附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华:必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功