没有合适的资源?快使用搜索试试~ 我知道了~
URL:http://www.elsevier.nl/locate/entcs/volume 19. html22页s行为的共等式方法Corina C irstea1英国牛津大学计算机摘要一个coalgebraic,方程的方法来指定的观测结构,允许选择的结果类型的意见。 其结果类型被构造为基本类型的余积的余代数操作被认为是,和概念的余项,协变量和coequation,对偶项,变量和方程的代数概念,用于指定通过这些操作观察到的结构,并约束其行为。一个健全的和完整的演绎演算推理的观测性质表示的余方程,然后制定。1介绍余代数理论的最新发展已经证明了余代数技术对于基于状态的动态系统的具体化的适用性[5,7,8]。这种技术在指定对象的观测性质方面特别富有成效,最终/余自由余代数为对象指定提供了适当的表示[3,2]。关于状态观测的各种推理方法也被提出:在[4,6]中,模态逻辑的思想被应用于余代数,产生了其句子约束单个状态观测的逻辑,而在[1]中,等式句子被用来关联同一状态的不同观测。 一方面,源于模态逻辑的方法可以提供余代数的特征性结果,但代价是使用有限句,见[4];但在这种方法中,完备性结果的公式化需要限制到有限句,以及所讨论的内函子满足一些相当严格的有限性条件,见[6]。另一方面,等式句的表达能力不足,1研究由ORS奖和牛津奖学金资助1999年由ElsevierScienceB. V. 操作访问和C CB Y-NC-ND许可证。2类似的特征化结果;然而,等式方法不需要任何额外的假设来导出完整性结果,参见[1]。此外,等式句子似乎更适合于具体化在煤格的整个状态空间上量化的观测性质(而模态逻辑公式似乎更适合于表征单个状态)。由于我们的目的是有效地推理状态观测,我们将集中在方程的方法。在[1]中,适当限制的代数项用于表示特定的状态观测,并且方程用于将这些观测联系起来。一个健全的和完整的推导演算方程,然后制定。然而,[1]中代数语法的使用阻止了该方法适应结构化结果类型的操作,将该形式主义中指定的行为类别具有结构化结果类型的操作对于捕获终止以及指定结构可变的系统是必不可少的;特别是,在某些系统状态中某些子系统的缺失可以通过这样的操作自然地捕获本文扩展了文献[1]中的方法,以适应其结果类型被构造为基本类型的余积的通过从一个本质上代数的框架移动到一个coalgebraic的,某些代数功能,如使用数据值作为(常数)observa- tions或使用数据参数的操作被丢弃。我们的方法可以很容易地进行调整,以包括这些功能。然而,我们认为它们的积分应该在不同的层次上进行,在那里应该可以在余代数指定的状态空间上指定任意的代数结构。在[1]中使用代数项来表示状态观测值不能沿用到我们的形式主义中,原因是在运算的结果类型中存在选择。因此,我们引入了一个概念的coterm提供了替代方案进行观察,这取决于最近评估的操作所产生的结果的类型。等式句子,然后用来约束观察,并制定了一个健全的和完整的演绎演算推理相关的行为我们假设熟悉代数规范的基本概念,以及基于状态的系统规范的共代数方法(The读者可以参考[8],以获得对余代数理论的全面介绍本文件的结构如下。第2节介绍了一个syn- tax,用于指定通过允许选择结果类型的操作可观察到的行为:析构函数签名上的余项用于描述由连续应用这些操作组成的观察,协变量在余项中用作其可能结果的占位符。在将析构函数签名的模型定义为由这种签名诱导的内函子的余代数之后,第3节提供了对3析构函数签名的最终余代数的元素,以及相关的双相似性概念。第4节介绍了一个约束状态观测的方程框架(通过将不同的观测联系起来),并说明了这个框架中特定的约束类型,而第5节则给出了一个完善的共方程演绎演算。第6节将这里提出的方法与[1,6]中的方法联系起来。最后,第7节总结了结果,并概述了未来的工作。2余签名、余变量、余项和替换所有即将到来的定义都需要一个固定的数据宇宙。因此,我们让V表示一个集合(可见排序),让D表示一个V-排序的集合(数据值),对于每个v∈V,Dv/=n。定义2.1析构函数签名(在D上)是一个对(H,N),其中H是隐藏排序的集合,N是析构函数符号的H×S+排序的集合(其中S=VNH包含所有的排序,而S+表示有限的非空排序序列的集合)。我们写δ:h→s1... sn对于δ ∈H,s1. sn.我们只假设析构函数的集合是可编译的。然而,在实践中,在大多数情况下,它是有限的。析构函数符号指定观察系统状态的基本方法。然后,通过coterm的概念形式化任意状态观测,它为所有可能的结果类型的析构函数提供了替代方案协变量在协项中用作其潜在输出的占位符,其方式类似于使用变量作为代数项输入的占位符定义2.2令(H,H)表示析构函数签名,令C表示(协变量的)S-排序集合具有来自C的协变量的S-余项的(S-排序)集合T[C]是满足以下条件的最小S-排序集合:• Z∈T<$[C]s,对于Z∈ Cs和s∈S• [t1, .. . ,tn]δ∈T<$[C]h,其中δ∈T <$h,s1. . sn和ti∈T∈[C]si,i=1, . . , ns∈S的余项(T∈[C]s的元素)指定了观察s类型状态的方法。余项的结果类型由其中出现的协变量的种类决定我们注意到,在空的协变量集上没有协项记法2.3对于一个协变量集C,如果Z∈Cs,我们记Z:s。 此外,实际出现在余项t∈T∈[C](一般来说,C的子集)中的协变量的(S-排序)集合被表示为covar(t)。例2.4使用可见排序1(由D解释为一点集)和Elt(表示列表元素的类型),隐藏排序List和NeList,以及操作符号来指定列表(finite或infinite)::List→1 NeList(用于将列表分为空列表和非空列表),head:4联系我们NeList→Elt(产生非空列表的头)和tail:NeList→List(产生非空列表的尾 下面是排序列表的余项:[F,N]?(用于观察列表是否为空),[F,[E]head]?(用于观察列表的第一个元素),[F,[[F,[E]head]?]尾]?(用于观察第二元素)等等。这些余项的结果类型分别为:1 +NeList、1 + Elt和1 + Elt。 (最后一个协项的结果类型为1 +Elt,而不是1 + 1 +Elt的原因是它使用了同一协变量的两次出现,而不是两个不同的协变量,排序为1。例2.5二叉树使用可见排序Leaf,隐藏排序Tree和NLeaf,以及操作符号来指定 。 : Tree→Leaf NLeaf ( 将 树 分 为 叶 子 和 非 叶 子 ) 和 left , right :NLeaf→Tree(分别生成树的左、右子树,而不是叶子)。值 得 注意的是,树的标准析构函数,即d:Tree→Leaf+(Tree × Tree),被分解为析构函数签名所需的 三 个析构函数。协变量的协项替换现在定义如下。第 二 章. 6Ift∈T∈[{Z1 , . ., Zn}]h, 其中hZi :si,i=1, . .,n,且ndifti∈T∈[C]si,其中i=1, . . ..,tn对于Z1,. ,Zn,表示为[t1/Z1,. ,tn/Zn]t(简称[t/Z] t)根据t的结构归纳定义如下:• [t/Z] Zi= ti,对于i = 1,. ,n• [t/Z]([tJ1, . . ,tJm]δ)=[[t/Z]tJ1, . . ,[t/Z]tJm]δ,对于δ∈φh,SJ1. . sJm 且tJ∈T[{Z1, .. . ,Zn}],j=1, . . ,m.公式2.7Givent∈T[{Z1, . . ,Zn}]h,其中hZi:si,i=1, . . ,n,且nd给定tJ∈ T<$[C] h,记t≤ tJ当且仅当存在t1∈ T<$[C] s1,. ,tn∈T∈ [C] sn使得TJ=[t1/Z1,.,tn/Zn] t。符号2.8对于tT [Z1,.,Zn],我们将t写为具有以下性质的余项:• t∈T<$[{X1, . . ,Xm}]仅包含一个变量的同时发生• t = [Z11/X1,... ,Zim/Xm] t,其中Zi1,...,Zim ∈ {Z1,.,Zn}。也就是说,t是从t通过重命名(并可能识别)它的一些协变量而获得的。(We注意,t仅定义为其协变量的双射重命名)。注2.9余项可以表示为树,其叶子用余变量标记,内部节点用运算符号标记:• 协变量Z表示为具有一个节点的树,标记为Z• 形式[t1,. .. ,tn.5∈→◦∈ ∈CDDS∈C在例2.4中,与[F,[E]head]关联的树? 是c?是的 ......F头,,,E3余代数、终结性和双相似性析构函数签名的模型为析构函数的排序和操作符号提供了特殊的解释定义3.1令(H,H)表示D上的析构函数签名。(D上的)S-余代数由S-序集C给出,使得Cv=Dv对于每个v∈V,以及,对于每个δ:h→s1. sn在ε中,函数δC:Ch→Cs1+. +Csn(+表示集合中的余积)。给定n-余代数A和C,n-同态f:A→C由S-排序函数(fs)s∈S给出,其中fs:As→Cs,其中s∈S,另外满足:• fv= 1Dv对于每个v∈V• [i1 fs1,. ,ln<$fsn](δA(a))= δC(fh(a))对于每个δ:h→ s1.snin n和eachaAh(其中eij:Csj Cs1+. . +Csn,对于j=1, . . , n是联产物注射)。我们用Coalg(n)表示对象是n-余代数,箭头是n-同态的范畴.记法3.2给定一个Z-余代数C,一个集合{Z1,.,Zn}的协变量,其中,对于i= 1,. ,n和协变量Z∈ {Z1,. ,Zn},记为:+Csn用于相应的联产物进样。定义3.3设f表示析构函数签名。一个余代数C中余项t∈T<$[C]的解释,记作tC,定义如下:• ZC=IZ,对于Z∈ Cs和s∈S• ([t1, .. . ,tn]δ)C=[(t1)C, . . ,(tn)C] δC为δS1... . sn和tiT[]si,i = 1,. ,n其中[(t1)C,. ,(tn)C]: Cs1 +……+ C s n →表示唯一的由(ti)C:Csi→s∈S Z∈CsCs,i = 1,. ,n.s∈S Z ∈Cs下一个结果涉及模型的析构函数签名与coalgebra的endofunctors诱导这种签名。命题3.4令(H,H)表示析构函数签名,令S = V <$H。设S是S -序集的范畴S-序集的可见序分量是S -序集的可见序分量。元由D和S-排序函数给出,其可见排序分量由1D表示。最后,设G为:SetS→设置D由以下人员提供:•G(X)v=Dv,对于v V•G(X)h=δ∈ θh,s1...Sn(Xs1+. + Xsn),对于h∈ H6DD∆a,h∆a,ha,ha,h⟨⟩∈ ∈ ∈∈a,ha,h∆C然后,范畴Coalg(G)和Coalg(G)是同构的。证明(略)C-余代数C唯一决定集合S-箭头γ:C→G_(C)(其h-分支映射c∈C_h到(δC(c))δ∈C_h,s1. s n(对于每个h∈H),反之,任何这样的集合S-箭在其整环上唯一地导出一个S-余代数结构.✷使用给定的析构函数集可观察到的抽象行为的特征析构子签名的最终余代数的存在性是命题3.4和关于ωop-连续内函子的最终余代数的存在性的一般结果的直接结果(参见例[8])。在这里,我们给出了一个替代的证明存在这样的final余代数,此外,提供了一个具体的描述其元素。定理3.5(最终余代数)任何析构子签名都存在最终余代数。证据 对于h ∈ H和一个协变量集C,设T1[C] h<$T<$[C] h由C中每个协变量只出现一次的余项组成.我们求出T1=( T1[C]h)/≤ λ≥.(报价由y≤n≥i确定)余项是相同的,直到它们的协变量的双射重命名即T1包含协项的等价类,其中协变量可能只发生一次。为了简化符号,我们将通过使用任意选择的代表来指代这样的等价类。最后,对于每个h∈H,我们令Dh={n}。我们现在定义一个F-余代数F:Fh={<$Zt,dt <$t∈T1|Zt∈ covar(t)s,dt∈ Ds其中s ∈ S,((t,tJ∈T1 ,tJ= [t1/Z1,.,tn/Zn] t,Zt= Zk)(ZtJ∈covar(tk)and(tk=ZtJ<$dt=dtJ))}对于h∈H,且:[Z1, . . . ,Zn]δh asvalue<$Z,d<$其中Z:v,d∈Dv,v∈VδF(δ)=Z[Z1,.,tJ,...,Z n] δ,d[Z1,...,tJ,...,Z n] δ τtJ∈T 1如果在[Z1,.. .,Zn] δ有值J伊拉克,h其中Z:hJ,d∈DhJ,hJ∈H对于 Fh,δS1... sn,h H和SiS,i = 1,...,n. 也就是说,F的元素是观测索引对协变量,在协项替换下是相容的值。故F是一个最终的余代数。因为,给定一个任意的n-余代数C,可以通过将状态c∈Ch映射到其中Zt和dt由tC(c)唯一确定,eacht∈T1:ift∈T1[{Z1, . . ,Zn}]h,其中hZ1:s1, . . ,Zn:Sn且iftC(c)∈7DJ∼ ∼ ⊆∼∈∼∈ C∈n ∈CZi(Csi)对于某个i∈ {1,.,n},则Zt=Zi dt.=tC(c)如果si∈V.如果si∈H上面的定义确保f是一个n-同态。 此外,任何从C到F的n-同态必然以这种方式定义。✷注3.6如果C ∈|集合S|设C上的余自由余代数是C上的余代数,在定理3.5的证明中,当h∈H时,Dh=Ch(而不是Dh={H}下一个结果给出了与析构函数签名相关的双相似性概念的特征定理3.7(双相似性)设C表示一个析构子签名,C表示一个C-余代数. 则两个状态c,CJ∈ Ch,h ∈ H是双相似的当且仅当对任意协变量集C和任意t ∈ T<$[C]h,存在s ∈ S和Z∈ Cs使得tC(c),tC(CJ)∈IZ(Cs),并且当s ∈ V时,tC(c)= tC(CJ).证据 我们证明,关系定义为:• c∈vcJ当且仅当c=cJ, 对于v∈V• c<$hcJ当且仅当对任意t∈T<$[C]h,tC(c),tC(cJ)∈IZ(Cs),Z∈Cs且s∈S,且当s∈V时,tC(c)=tC(cJ), 对于h∈H是C上的互模拟,并且C上的任何互模拟都包含在C中。为了证明这是一个互模拟,我们设c,cJ∈Ch,其中c∈hcJ,δ ∈ h,s1. Sn,并证明了δC(c)<$δC(CJ). 取t = [Z1,.,Zn] δ给出δC(c),δC(cJ)∈iZi(Csi),其中i∈ {1,.,n},其中Zi:si,且当si ∈ V时,δC(c)= δC(CJ).我们区分两种情况:(i) si=v∈V。 δC(c)≠vδC(cJ)的事实则直接由δC(c)= δC(c)。(ii) si=HJ∈H. 为了证明δC(c)<$hJδC(cJ),我们设tJ∈T<$[CJ] hJ,对于某个协变量集CJ,然后设t = [Z1,.,tJ,. ,Zn] δ.由于c),tC(cJ)∈iZ(Cs{Z1,.,Zi−1,Zi+1,.,Zn})s,其中s∈S;此外,如果s∈V,则tC(c)=tC(cJ)。 则δC(c),δC(cJ)∈iZ(ChJ)给出TJC(δC(c)),TJC(δC(cJ))∈对于Z∈CsJ和s∈S,ιZ(Cs),且更进一步,tCJ(δC(c))=tC(c)=tC(cJ)=tJC(δC(cJ)),如果s∈V. 也就是说,δC(c)<$hJδC(cJ)。因此,互模拟是一种互模拟。为了证明j是C上最大的互模拟,让J表示C上的任意互模拟。如果h∈H且c,CJ∈Ch使得CJhCJ,则可以通过对tT <$[ ]h的深度的归纳证明,对于某些Zs和s S,tC(c)和tC(CJ)都在iZ(Cs)中,而且,如果s V,那么它们重合。(The这里使用了J因此,CHCJ。因此,J。 证明到此结束✷推论3.8设f表示一个析构函数签名,F表示一个最终的f-co代数ra ,l,r∈Tf[{Z1, .. . . ,Zn}]h与hZ1:s1, . . ,Zn:Sn,h∈H.8则对f∈Fh,lF(f)=rF(f)当且仅当对任意协变量集C和任意ti∈T[C]si 对于i=1, . . ,n,([t1/Z1, . . ,tn/Zn]1)F(n)和([t1/Z1,.,tn/Zn] r)F(n)对某些Z∈Cs和s∈S都在<$Z(Fs)中,而且([t1/Z1,.,tn/Zn] 1)F(n)=([t1/Z1,...,tn/Zn] r)F(n)当s∈V时.证据 只有方向是直接的。 在if方向上,证明了lF(f)和rF(f)是双相似的.取ti= Zi,i = 1,.,n给出lF(n),rF(n)∈iZi(Fsi),其中i∈ {1,.,n}。然后,对于任意t∈T∈[CJ]si,对于任意可变变量tCJ,取tj=Zj,其中j∈{1, .. . , i−1, i+1,.,n}和ti= t的假设给出tF(lF(n))= tF(rF(n)).因此,lF()si rF(),则产生lF()= rF()。✷4Coequational Specifications在代数规范中,人们使用方程来约束代数对项的解释类似的方法可能证明适合于约束状态观测,只要人们只对同一状态的不同观测相关感兴趣。本节正式定义余方程和余代数满足,并说明它们能够捕获的约束类 型 。余方程概念的第一个近似是由一对同类余项给出的。一个余代数对一个余方程的满足则对应于该余代数为两个余项提供了相似的解释。例如,形式为:[[F,[E]head]?]尾巴=[E]head限制NeList在任何余代数C中的解释,满足它恒定,无限列表(因为它需要[[F,[E]head]?]尾C,1E头C:CNeList→C1+CEltoyielddsimilarresultsonynon-emptylist)。然而,由于存在的选择,在结果类型的操作,一个预期的推理与coequations涉及某种形式的情况下分析的结果类型的coterms。例如,为了导出余方程:[[F,N]?]尾巴=[[尾巴(通过要求[iF,iN]<$[[F,N]?]尾C,[iFJ,iN][[F ',N]?] tailC:CNeList→C1+ C1+ CNeList得到类似结果),对[[F,N]?]应该进行跟踪。具体地说,上述余方程的满足将通过考虑[[F,N]?]的所有可能结果类型来实现。tail(在本例中,1和NeList),并表明结果类型与NeList不同的假设以及第一个协方程产生了矛盾。为了得到完整的推论对于余方程的微积分,这种形式的案例分析应该被包含在余方程的概念中。这就解释了以下定义。9→∈ ∈{} ∈定义4.1设f表示析构函数签名。 一个协方程是一个tuple((l,r),(t1,C1J), . . ,(tn,Cn,J)),als0表示dl=rif(t1,Cn,J), . . ,(tn,CnJ),其中l,r ∈ T<$[C] h且ti∈ T<$[Ci] h,CiJ<$Ci,i = 1,. ,n. 一个余代数C满足一个上述形式的余方程e(记作C |=e)当且仅当lC(c)= rC(c)成立,只要c ∈ Ch使得(ti)C(c)∈ iZi(Csi),对某个Zi∈(CiJ)si,对于i=1, . . ., n(在hichi被设置为满足不同条件(ti,C1,J), . . ,(tn,CnJ))。记法4.2如果CiJ={Zi},我们有时把(ti,CiJ)写成(ti,Zi例4.3给定例2.4中的析构函数签名,余方程:[[F,[E]head]?] tail= [E]headif([[F,N]?]尾,N)将NeList的解释限制为常量、有限或无限列表。类似地,共方程:[[F,[[F ',N]?] tail]?] tail= N if([[F,[[tail]?]尾,N)将NeList的解释限制为交替列表。例4.4由多个相邻有向线段组成的连接使用隐藏排序指定:点、线段和连接,以及操作符号:x,y:点→整数,源,目标:段→点,第一:连接→段,其余:连接→1连接,进一步由以下coequation约束:[[P]target]first= [F,[[P]source]first]restif([F,C]rest,C)捕获关于构成连接的段的共享条件余方程的满足性既被余代数同态保持又被余代数同态反射。命题4.5设C,D表示n-余代数,设f:C D表示ae-同态,设e表示一个e-余方程。然后:(i) C| f=Im(f)|=e(ii) D|=e隐含C|e。证明(草图)tIm(f)(fh(c))=[ι1<$fs1,.,in<$fsn](tC(c))对于每个hH,t T [Z1,.,Zn] h,其中Z1:s1,.,Zn:sn和cCh是采用(This这是一个定义的结果,一个同态)。✷因此,满足一组余方程的余代数类在子余代数、同态像和有限余积下是闭的,即它是一个共变种(见[8])。推论4.6满足一个余方程集的余代数形成余簇.10∈∅|∆∆J记法4.7给定δ ∈ H,s1. sn,i∈ {1,.,n}和形式(tj,CjJ)j=1,. ,m对于sortsi,我们写[Z1,.、C、.,Zn] δ作为([Z1,. ,tj,. ,Zn] δ,CjJ{Z1,. ,Zi−1,Zi+1,. ,Zn})j=1,. ,m,具有协方差(tj){Z1,. ,Zi−1,Zi+1,. ,Zn}= 0,其中j = 1,.,m.同样,给定t∈T[{Z1, .. . ,Zn}]h和i,C如上所述,我们表示[Z1/Z1, . . ,C/Zi, . . ,Zn/Zn]t对于([Z1/Z1,. ,tj/Zi,. ,Zn/Zn] t,CjJ{Z1,.,Zi−1,Zi+1,.,Zn})j=1,. ,m.定义4.8析构函数规范是一个对(E,E),其中E是析构函数签名,E是一组析构余方程。一个C-余代数C满足一个析构子规范(E,E)(记作C|=E)当且仅当C|对于每个e∈E, 一个析构函数指定(E,E)被称为不一致的w.r.t. 隐藏排序hH当且仅当Ch= 当C=E时,因为任意的余代数C.一组E-余方程在语义上蕴涵一个E-余方程e(记作E |= E)当且仅当C |=E隐含C|=对任何C.余代数记法4.9给定一个余方程组E和h∈H,我们记为Eh为E的子集,由排序h的余方程组成。最终余代数的存在性从析构器签名推广到析构器规范,析构器规范的最终余代数是底层签名的最终余代数的子余代数命题4.10令(E,E)表示析构函数的具体化。 存在一个final(E,E)-余代数.证据设F表示一个final余代数,并设:FE,h={F ∈ Fh|(lF(tF(k))= rF(tF(k)),当t∈T1[{Z1, . . ,Zn}]h, i∈{1, . . ,n}且(l=rifC)∈Es使得tF(ε)∈IZi(Fsi)且C在tF(ε)中成立,h∈H FE,v=Dv,v∈V则(FE,s)s∈S定义F的一个π-子余代数。对于,给定f∈FE,h和δ∈θh,s1.. . sm,sayδF(f)∈isj(Fsj)其中ithj∈{1, .. . . ,m},lF(tJF(δF(δ)=对于任意的YTJ∈T1[{Z1, . . ,Zn}]s(其中Zk:sJk,对于k=1、...,n)和任意余方程(l = r,如果C)∈E,使得C在TJF(δF(n))中成立.这可以从t∈FE,h通过取t = [X1,.,Xj−1,tJ,Xj+1,.,Xm] δ.另外,给定任意的(E,E)-余代数C,!通过将FE包含到F中,将C从C因子转换为F因子。(命题4.5给出Im(!C)|= E,而FE是,根据定义,满足E中余方程的F的最大子余代数。所以,!C:C→F定义了一个从C到FE的n-同态。这样一个同态的唯一性则由从C到F的一个n-同态的唯一性推出。✷最终余代数作为析构子规范的表示的适用性由以下结果进一步证明我11/.∆定理4.11设(E,E)表示一个析构函数,设e表示一个设FE表示一个最终的(E,E)-代数. 然后,E|当且仅当FE|e。证据 if方向遵循命题4.5,而only if方向遵循FE|=E。✷与代数相反,其中形式X=XJ的方程仅由其对应的载体是一点集的代数满足,在余代数中,形式Z=ZJ的余方程仅由其对应的载体是空的余代数满足。更一般地,形式为l=r且covar(l)=covar(r)的协方程将l和r的结果类型约束为在l和r中都出现的协变量的类型。在这样的余方程中,特别感兴趣的是l和r相同的那些,直到它们的协变量的重命名。定义4.12令T表示析构函数签名,令t∈T<$[C]h对于某个协变量集合C和某个h∈H,令CJ <$C。余方程:t= [y1/X1,. ,ym/Xm] t其中:• t= [Z11/X1,...,Zim/Xm] t (见注释2.8)• y=Xj如果Zij∈CJ对于j = 1,. ,mJYj/=Xj如果Zij/∈ CJ被称为t的类型约束,记为c(t,CJ)。对t的类型约束将t的结果类型约束为CJ中的一个协变量的类型:给定一个余-余代数C,c(t,CJ)在状态c∈Cn中成立当且仅当tC(c)∈iZ(Cs),对于某个Z∈CSJ。记法4.13我们有时写c(t,Z),对于c(t,CJ),其中CJ={Z}。Remark4.14Ift∈T1[{Z1, .. . ,Zn}]和ndi∈{1, . . ,n},则nc(t,Z1)具有形式t = [Y1/Z1,.,Zi/Zi,.,Yn/Zn] t.例4.15给定例2.4中的析构函数签名,类型约束c([[F,N]?]尾,N)具有以下形式:[[F,N]?]尾巴=[[尾巴这个余方程将NeList在满足它的余代数中的解释限制为无限列表(因为它要求在任何这样的余代数中对尾的解释总是产生非空列表)。12CC5共等式演绎我们现在能够为余方程制定一个健全而完整的演绎演算。我们考虑以下演绎规则:[base]Eee∈E[cond-base]Ec(t,C)if(t,C)[弱化]Et=tJ,如果CEt=tJ如果C,CJ[回复率]Et=t[对称性]Et=tJ如果CEtJ=t ifC[transitivity] Et= tJ如果C, EtJ= tJJ,如果CEt=tJJ,如果C[闭包]Et1= tJ1 如果C1,. ,Etn= tJn如果CnE[t1, .. . ,tn]δ=[tJ1, . . ,t,J,n]δif[C1, . . ,Zn]δ, . . ,[Z1, .. . ,Cn]δ[替换]Et=tJ,如果CE[t1/Z1,. ,tn/Zn] t = [t1/Z1,. ,tn/Zn] tJ,如果C[矛盾]Et=tJ如果C如果C,则E= rt,tJ∈T [C]h,l,r∈T [CJ]hcovar(t)covar(tJ)= covar(t j)[团结] 如果(t,Z),(tJ,Z)Z:v,|Dv|= 1个[案例分析] 如果Ci(t0,C1),.,Et = tJif Ci(t0,Cn)Et=tJ,如果Ct,TJ∈T<$[CJ] h,t0∈T<$[C] h,C = C1<$. Cn定理5.1(合理性)设(E,E)表示一个析构子,e表示一个余方程。那么,Ee意味着E|e。证据 我们使用归纳法对E e的证明结构进行说明,Ee意味着E|e。如果最后应用的规则是base,则E|从A的定义可以得出:|对于一个余代数A,A = E.如果应用的最后一个规则是弱化,则E| = t = tJif C,CJ从以下事实得出:如果C和CJ在状态a∈Ah中成立,则C在a中成立。如果应用的最后一个规则是条件基或反射性,则E| = Ee跟随任何满足形式c(t,)的任何余方程的E-余代数(因此也跟随任何(E,E)-余代数),如果(t,),分别为t = t。如果应用的最后一个规则是对称性、传递性或替换性,13则E|从归纳假设中得出,14►CCE、hE、hE、hE、ha,ha,h平等的如果最后一个规则是闭包,则对任何(E,E)-余代数A且任意a∈Ah满足[C1,. ,Zn] δ,. ,[Z1,. ,Cn] δ,称δA(a)∈iZi(Ai)其中i∈ {1,.,n},[Z1,.,Ci,.,Zn] δ by a暗示Ci满足δA(a),得到(ti)A(δA(a))=(TJi)A(δA(a))(通过归纳),即([t1, . . ,tn]δ)A(a)=([tJ1, . . ,tJn]δ)A(a). 如果最后一个规则是矛盾,则E|=l = r,如果C从以下事实得出:对于一个(A,E)-余代数A,没有状态a∈Ah满足C(因为它们必须满足tA(a)= tJA(a))。 如果应用的最后一个规则是单位,则tA(a),tJA(a)∈iZ(Dv),|Dv| = 1,则对任意的余代数A和任意的状态a∈Ah,tA(a)= tjA(a).最后,如果应用的最后一个规则是案例分析,E|如果C从(t0,C1),.,(t0,Cn)对任意(n,E)-余代数A,在满足C的任意状态a ∈ Ah中成立.✷为了证明演绎演算的完备性(即E |=e对于任意的E和e,我们首先需要一些初步的结果。引理5.2设E表示析构函数签名,设E表示- 余方程 如果El = r如果Ci(t, )和Ec(t, )如果C,CJ,则EL=r如果C,CJ.证明(略)通过实例分析和对比,得出结论:El=r ifC,CJ,(t,C)和El=r ifC,CJ,(t,CJ),CJ=covar(t)\C.✷引理5.3设(E,E)表示一个析构子,FE表示一个最终(E,E)-余代数。 设h∈ H,C表示h的某些条件. 若E/rl = r若C对任意l,r∈T<$[C] h,且covar(l)∈covar(r)= r,则F C={f ∈ FE,h|C保持在/=中。证据 我们在Set中定义一个ωop-链,它具有以下性质:(a) FC投射到这个ωop-链的极限对象L上(b) 若L=T,则E∈L=r若C有l,r∈T∈[C]h,则covar(l)∈covar(r)=T。则FC=F蕴涵L=F(因为存在FC的满射到L),这反过来又意味着E<$l=r,如果C对某个l,r∈T<$[C]h,covar(l)covar(r)=,产生矛盾。我们首先注意到,集合T1是可重复的(因为T是);假设T1={t1,t2,. }。我们考虑下面的ωop链:p1p 2p 3C1,rC2,rC3,r.其中:Cn={(Zt1,.,Ztn)|Zti ∈covar(ti),其中i∈ {1,.,n}如果Ci(t1,Zt1),.,(tn,Ztn)对任意l,r∈T<$[C]h,其中covar(l)<$covar(r)=<$}15E、hE、ha,hE、h∆1nE、h我我我我我以及:pn(Zt1,.,Ztn+1)=(Zt1,.,Ztn)对于n = 1,2,. . 然后,该ωop链的极限对象L由下式给出L={(Zti)i∈{1,2,. 个文件夹|如果Ci(t1,Zt1),. ,(tn,Ztn)对任意l,r∈T<$[C]h,其中covar(l)<$covar(r)=<$且任意n}为了证明(a),我们证明了:}∈ F C›→(Zt)i∈{1,2,. }∈L我定义了一个从FC我去洛E,H,I为了正确地定义这个映射,我们必须证明(Zti)i∈{1,2,.. }∈L对于每个f∈FC. 但如果Ci(t1,Zt),.,(tn,Zt),对于某个CE、h,一些l,r∈T<$[C] h,其中covar(l)<$covar(r)= ∞,一些n∈ {1,2,.个文件夹与演绎的合理性一起将产生矛盾(因为C并且每个(ti,Zi),其中i = 1,.,n,在f∈FC中成立,而l = r不成立)。我们现在知道有这样一个映射→(Zti)i∈{1,2,. }是满射的。为此,我们首先对每个s∈S固定ds∈ Ds。然后,给定(Zti)i∈{1,2,. }∈ L,我们构造通过令<$i=<$Zt,dt<$i∈{1,2,. },其中dt= ds,如果Zt:si,si∈ S.因此,若hatt∈Fh,letti,tj∈T1,则hattj=[t1J/Z1, . . ,tJn/Zn]ti.如果Zti=Zk,我们必须证明Ztj∈covar(tjk),而且,如果tjk=Ztj,则dti=dtj。设Ztj/∈covar(tJk).然后:E=[tJ1/Z1, . . ,tJn/Zn]ti(后接反应性)连同:E =[U1/Z1,.,Zk/Zk,...,Un/Zn] ti,如果Ci(t1,Zt1),...,(ti,Zti)以及:E=[V1/Z1],. . ,Ztj/Ztj, . . ,Vm/ZmJ]tjifCi(t1,Zt1), . . ,(tj,Ztj)(both接着是条件基和弱化)产生(通过替换,接着是弱化,然后是传递性):E=[V1/Z1],. . ,Ztj/Ztj, . . ,Vm/ZmJ]tj=[U1/Z1, . . ,tJk/Zk, . . ,Un/Zn]ti如果Ci(t1,Zt1),.,(tN,ZtN)其中N=max(i,j)。但是最后一个协方程的lhs和rhs没有共同的协变量,因此与L的定义相矛盾。因此,Ztj∈covar(tJk)。此外,如果tJk=Ztj,则si=sj,这给出dti=dtj。Toshowthat∈FE , h ,lett∈T1[{Z1 , . .,Zn}]h ,i∈{1 , . .,n} 且F16(ti=tJifCi)∈Ebesucht ttF(n)∈IZi(Fsi),ti,tJi∈Ti[Ci]si 且Ci在tF(ε)中成立. 我们必须证明(ti)F(tF())=(tJi)F(tF())。 根据推论3.8,它表明,对于任何余项u1,…,uq的合适值17►E、hE、h◦ ◦∈{}∈→1M∆1p∆排序,或者对于某个Z:h,lF(),rF()∈iZ(Fh),或者对于某个Z:v,lF(),rF()∈iZ(Dv),并且在最后一种情况下lF()=rF(),其中:l = [u1/U1,. ,uq/Uq][Z1/Z1,. ,ti/Zi,. ,Zn/Zn] tr=[u1/U1, . . ,uq/Uq][Z1/Z1, . . ,tJi/Zi, . . ,Zn/Zn]t其中{U1,. ,Uq}= Ciii {Z1,. ,Zi−1,Zi+1,. ,Zn}。Weletl=[Vi/Xl, .. . ,Vi/Xm]l,其中hl∈T1[{X1, . . ,Xm}]h,和ndr=[Vj/Y1, .. . ,其中r∈T1[{Y1, .. . ,Yp}]h(参见记法2.8)。FromE ti=tJi如果Ci,我们可以通过连续应用闭包规则和替换来推断:如果[Z1/Z1,. ,Ci/Zi,. ,Zn/Zn] t如果Zl= Xk且Zr= Yl,则Vik= Vjl.因为,如果情况不是这样的话,cond-base加上置换将产生:E[S1/V1,.,Vik/Vik,.,S0/V0] 1 = [T1/V1,...,Vjl/Vjl,. , To/Vo] r如果[Z1/Z1,.,Ci/Zi,.,Zn/Zn] t,(1,Xk),(r,Yl),其中Vik/= Vjl,这将产生:E[S1/V1,.,Vik/Vik,.,S0/V0] 1 = [T1/V1,...,Vjl/Vjl,. , To/Vo] r如果(t1,Zt1),.,(tN,ZtN)对于N足够大(事实上[Z1/Z1,. ,Ci/Zi,. ,Zn/Zn]t与引理5.2一起在这里使用)。但这与L的定义相矛盾。因此,Vik=Vjl=Z:s且lF(k),rF(k)∈iZ(Fs)。此外,如果s=v,对于某个v∈V,lF(n)=rF(n)由lF(n)和rF(n)都等于dv而得。因此,f∈FE,h。此外,我们有<$∈FC。 如果不是这样的话,那就...在C中的操作将与(t1,Zt1)矛盾,...,(tN,ZtN),其中N足够大(根据引理5.2),因此我们可以推断出E_1 = r,如果C_1(t1,Zt1),.,(tN,ZtN),其中covar(l)为ωcovar(r)= ω。这就证明了FC有一个到L的满射为了说
下载后可阅读完整内容,剩余1页未读,立即下载
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- GO婚礼设计创业计划:技术驱动的婚庆服务
- 微信行业发展现状及未来发展趋势分析
- 信息技术在教育中的融合与应用策略
- 微信小程序设计规范:友好、清晰的用户体验指南
- 联鼎医疗:三级甲等医院全面容灾备份方案设计
- 构建数据指标体系:电商、社区、金融APP案例分析
- 信息技术:六年级学生制作多媒体配乐古诗教程
- 六年级学生PowerPoint音乐动画实战:制作配乐古诗演示
- 信息技术教学设计:特点与策略
- Word中制作课程表:信息技术教学设计
- Word教学:制作课程表,掌握表格基础知识
- 信息技术教研活动年度总结与成果
- 香格里拉旅游网设计解读:机遇与挑战并存
- 助理电子商务师模拟试题:设计与技术详解
- 计算机网络技术专业教学资源库建设与深圳IT产业结合
- 微信小程序开发:网络与媒体API详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)