没有合适的资源?快使用搜索试试~ 我知道了~
自动机的代数-余代数对偶:变体和余变体的研究
×∼→→ →可在www.sciencedirect.com在线获取理论计算机科学电子笔记298(2013)7-28www.elsevier.com/locate/entcs语言的变体和共变体(扩展摘要)Jan Rutten1CWI和荷兰AdolfoBallester-Bolinches2EnricCosme-Ll'opez3在西班牙的V a l `Cirv a l`Ciru大学进行艺术创作摘要由于同构(X A)X=X(A)X),确定性的过渡结构具有状态集X和来自字母表A的输入的自动机可以被视为代数,作为余代数这种代数-余代数对偶可以追溯到Arbib和Manes,他们将其表述为可达性和可观 测性之间 的对偶 ,并 最终基于 系统理 论中的卡 尔曼对 偶。 最近, 它被用 来给出确 定自动 机的Brzozowski极小化算法的一个新的证明。在这里,我们将使用自动机的代数-余代数对偶作为研究变种和余变种的共同视角,这是分别由方程和余方程定义的自动机和语言的类别。我们首先与艾伦伯格的语言多样性定义联系起来关键词:自动机,簇,余簇,方程,余方程,代数,余代数。1介绍由于同构(X×A)→X= X→(A→X)具有状态集X和来自字母表A的输入的确定性自动机的转换结构可以被看作是代数[11]和余代数1电子邮件:janr@cwi.nl2电子邮件:Adolfo. uv.es3电子邮件:enric. uv.es1571-0661 © 2013 Elsevier B. V.在CC BY-NC-ND许可下开放访问。http://dx.doi.org/10.1016/j.entcs.2013.09.0058J. Rutten等人/理论计算机科学电子笔记298(2013)7∗C[19、20]。因此,簇的代数概念和余簇的余代数概念都适用。在本文中,我们提出了一个初步的版本,什么是成为一个系统的研究品种和共变的自动机和形式语言。我们将以通常的方式定义各种自动机(视为代数),如由方程定义的类[12]。自动机的余簇(被视为余代数)将是由余方程定义的一类[20]。然后,自动机的变种和余变种将被用来定义语言的变种和余变种。我们关于语言多样性的概念不同于艾伦伯格[12,18]的经典定义,我们将对这两个概念之间的关系做一些初步的观察我们调查的背景将是下图:1xc2,1,(1)JC ZArx Xo2一个人(This图将在第3节中更详细地解释。)在中间,我们有给定自动机的状态集X。在左边,A是A上所有单词的集合,在右边,2A是A上所有语言的集合。对于每一个点(初始状态)x∈X的选择,函数rx将任何字w发送到输入w上从x到达的状态xw。对于每一个着色(最终状态集)c:X→2的选择,函数oc将任何状态发送到它接受的语言点自动机A(以空词为点)和X(以点为点)x是代数。着色自动机2A(着色如后所述)和着色为c的X都是余代数。 函数(实际上是代数的一个同态)rx的唯一存在性由A的初始性导出。 而函数(余代数的同态)oc的唯一存在性由2A的有限性导出。(Sets的)方程将存在于我们的图的左而余方程(组)位于我们图的右因此,图(1)允许我们定义簇和上簇,并从一个共同的角度研究它们的性质图(1)的代数-余代数对偶是自动机[2,1]的可达性和可观测性之间的对偶的现代呈现,它最终可以追溯到系统理论[ 14,15 ]中的Kalman可控性和可(See[7,9]进一步的分类概括。最近[6,3],自动机的代数-余代数对偶被用来给出Brzozowski极小化算法[ 8 ]的一个新的证明和各种推广目前的工作在不同的方向,重点放在(共)方程和J. Rutten等人/理论计算机科学电子笔记298(2013)79JCZ(共)品种。值得注意的是,我们将进一步细化图(1)如下:1名c2,阿尔布费拉oAAfree(X,α)RxX余自由(X,α)oc_2(For详情见第5节) 新的图包括,对于每个具有转移函数α的自动机X:X→XA,(指向的)自动机自由(X,α),它表示由(X,α)满足的最大方程组并且,对偶地,我们将构造一个(有色)自动机cofree(X,α),它表示由(X,α)满足的最小余方程集。我们在上面已经提到,我们对语言多样性的定义不同于艾伦伯格 理解经典的多样性概念和现代的多样性概念之间的关系的第一步包括:我们有些惊讶-这个观察进一步暗示了有色自动机cofree(X,α)可以被看作是跃迁幺半群的对偶版本还有许多问题有待进一步了解。我们已经提到了与艾伦伯格簇定理的联系。此外,我们还想把当前的代数-余代数观点与最近各种语言的发展联系起来,特别是[13]和[4,5]。最后,沿着[6,3]的路线,应该可以将目前的设置从确定性自动机推广到其他结构,如Mealy机,加权自动机等。2预赛设A是一个有限的字母表,在我们所有的例子中固定为{a,b}。 我们把A记为A上所有有限序列(字)的集合。我们用ε表示空词,用vw表示两个词v和w的连接。对于集合X和Z,我们定义X Z={g|g:Z→X}。对于集合X,Y,Z和函数f:X→Y,我们定义fZ:XZ→YZ为fZ(g)=f<$g。我们定义函数f:X→Y的像和核为:im(f)={y ∈ Y |f(x)= y {x ∈ X,y}ker(f)={(x1,x2)∈ X × X |f(x1)= f(x2)}A上的语言L是子集L<$A<$,我们用下式表示A上所有语言的集合:2 A ={L|LA}(这里忽略,有时下面忽略子集和特征函数之间的差异)。对于语言L<$A<$且a∈A,我们定义L的a-导数10J. Rutten等人/理论计算机科学电子笔记298(2013)7⎨通过L a={v ∈ A<$|av ∈ L}我们更一般地定义,L w={v ∈ A}|wv ∈ L}我们定义L的初始值L(0)为:如果ε∈L,则L(0)=ε1如果ε/∈L,则为0对于函子F:Set→Set,F-代数是由集合S组成的对(S,α)函数α:F(S)→S。 一个F-余代数是一个对(S,α),其中α:S→F(S)。我们将使用以下functors:F(S)=SAG(S)=S×A(2×F)(S)=2×SA(1+G)(S)=1+(S×A)自动机一个自动机是一个对(X,α),由一个(可能无限)状态集X和一个转移函数α:X→XA在图片中,我们使用以下符号:阿伊什a(x)=y我们还将写xa=α(x)(a),更一般地说,xε=x xwa=α(xw)(a)我们观察到自动机是F-余代数。因为对于任意的A和X,(X):(X→XA)→((X×A)→X)自动机也是G-代数[17]。α(x,a)=α(x)(a)一个自动机可以用着色函数来修饰c:X→2使用基本颜色集合2={ 0, 1}。我们称状态x为接受(或最终),如果XJ. Rutten等人/理论计算机科学电子笔记298(2013)711c(x)= 1,如果c(x)= 0则不接受。 我们称三元组(X,c,α)为有色的12J. Rutten等人/理论计算机科学电子笔记298(2013)7XX自动机在图片中,我们使用双圆圈表示一个状态正在接受。例如,在下面的自动机中,一BB状态x是接受的而状态y不是。通过将函数c和α配对,我们看到着色自动机是(2×F)-余代数:βc,αβ:X→2×X一个自动机也可以有一个初始状态x∈X,这里用一个函数表示x:1 →X其中1 ={ 0}。我们称三元组(X,x,α)为点自动机。通过将函数x和αn配对,我们可以看到,将一个utomata映射为(1+G)-代数:[x,α]:(1+(X×A))→X我们称一个四元组(X,x,c,α)为一个有点有色自动机。我们可以用下面两个图中的任何一个来描述它1c21c2βz zXX,,αα˜JCXAX×A我们将使用左边的图表,这只是个人喜好的问题。我们进一步观察到,指出和彩色自动机被简单地称为自动机- tomata在大多数文献中的自动机理论。一个有点的有色自动机(X,x,c,α)既不是代数也不是余代数同态,子自动机,互模拟一个函数h:X→Y是自动机(X,α)和(Y,β)之间的同态,如果它使下面的图可交换:XhYαβJcXAYAhAx,,vy,,一一J. Rutten等人/理论计算机科学电子笔记298(2013)713此外,点自动机(X,x,α)和(Y,y,β)以及着色自动机(X,c,α)和(Y,d,β)的同态分别考虑初始值和颜色:1yXJC Z2,DXhYXhY如果在上面的图中X≠Y,并且(i)h是子集包含h:XXY(and,而且(ii)x=y或(iii)c=d),则称X为Y的(i)子自动机(分别为(ii)点和(iii)有色子自动机)。对于一个自动机(X,α),且x∈X,由x生成的子自动机,记为通过联系我们由X的最小子集组成,该子集包含x并且在转换下是封闭的。我们称一个关系R<$X×Y为自动机的互模拟,如果对所有的(x,y)∈X×Y,(x,y)∈R<$a∈A,(xa,ya)∈R(其中xa=σ(x)(a)且ya=τ(y)(a))。 对于点自动机(X,x,α)和(Y,y,β),R是点互模拟,如果(x,y)∈R.对于着色自动机(X,x,α)和(Y,y,β),R是着色互模拟,如果对所有(x,y)∈X×Y,(x,y)∈Rc(x)=d(y)互模拟E<$X×X称为X上的互模拟。 如果E是一个等价关系,我们称之为互模拟等价。X上互模拟等价的商映射是自动机的同态QXX/Eα[α]JcXA(X/E)AQA有明显的X/E,q和[α]的定义。如果等价E是(X,x,α)上的点互模拟或(X,c,α)上的着色互模拟,则我们还分别有,1[x]XJCTX2,[丙]XhX/EXhX/E又有明显的[x]和[c]的定义。CC14J. Rutten等人/理论计算机科学电子笔记298(2013)7¸如果z∈Y,则为β(z)(a)对于同态h:X→Y,ker(h)是X上的互模拟等价,im(h)是Y的子自动机.通过商同态和包含同态的任何同态h因子如下:Xα JcqAH[α]JCZY轴βiAJcXA(X/ker(h))AYAHA注意X/ker(h)= im(h)。 因为q是满射的,而i是内射的,所以对(q,i)被称为h的epi-mono分解。同余关系一个右同余是一个等价关系E<$A<$$> ×A<$,使得对于所有的(v,w)∈A×A,(v,w)∈E<$$>u∈A<$,(vu,wu)∈E一个左同余是一个等价关系E<$A<$$> ×A<$,使得对于所有的(v,w)∈A×A,(v,w)∈E<$$>u∈A<$,(uv,uw)∈E我们称E为同余,如果它既是右同余又是左同余。注意E是一个右同余i,它是(A,σ)上的互模拟等价。自动机的积和余积自动机(既是G-代数又是F-余代数,因此)既有积又有余积,如下所示。• 两个自动机(X,α)和(Y,β)的乘积由(X×Y,γ)给出,其中X×Y是笛卡尔积,γ:(X×Y)→(X×Y)Aγ((x,y))(a)=(α(x)(a),β(y)(a))• 两个自动机(X,α)和(Y,β)的余积(或:和)由(X+Y,γ)给出,其中X+Y是不交并,其中γ:(X+Y)→(X+Y)Aγ(z)(a)=α(z)(a)ifz∈X点自动机(是(1 +G)-代数,因此)有产品,如下。 两点自动机(X,x,α)和(Y,y,β)的乘积由(X×Y,(x,y),γ)给出,其中(X×Y,γ)如上所述,具有初始状态(x,y):1→X×YQX/ker(h)我J. Rutten等人/理论计算机科学电子笔记298(2013)715如果z∈Y,则有n(z)∗有色自动机(是(2×F)-余代数,因此)有余积,如下. 两个有色自动机(X,c,α)和(Y,d,β)的余积由下式给出:(X+Y,[c,d],γ),其中(X+Y,γ)如上所述,并且具有着色函数[c,d]:(X+Y)→2[c,d](z)=c(z)ifz∈X所有上述的二进制(共)产品可以很容易地推广到(共)产品的任意家庭的自动机。3设置场景集合A形成具有初始状态ε和转移函数σ的点自动机(A,ε,σ),其定义为:σ:A→(A)Aσ(w)(a)=wa它在以下意义上是初始的:对于任何给定的自动机(X,α),初始状态x:1→X的每一个选择都导出一个唯一的函数rx:A→X,由rx(w)=xw给出,它使得下面的图可交换:1xεJC ZArxXσ αJc(A)AXA(rx)A这个性质使得(A∈,ε,σ)成为初始(1+G)-代数.等价地,自动机(A,σ)是在集合1上自由的G-代数。函数rx将单词w映射到从输入w的初始状态x到达的状态xw,因此称为(X,x,α)的可达性映射。语言的集合2A构成一个有色自动机(2A,ε?,τ),着色函数ε?定义为ε?:2Aε→ 2ε?(L)=L(0)转换函数τ定义为τ:2A→(2A)Aτ(L)(a)=La它在以下意义上是最终的:对于任何给定的自动机(X,α),着色函数c:X→2的每一个选择都诱导出唯一的函数oc:X→2A,由下式给出:16J. Rutten等人/理论计算机科学电子笔记298(2013)7CC×∗∗Ho c(x)={w |c(x w)= 1},这使得下面的图可交换:2,ε?Xo2A双极晶体α τJcJcXA(2A)A(oc)A该性质使得(2 Aε,ε?,τ)final(2F)-余代数.等 价 地,自动机(2A,τ)是在集合2上余自由的F-余代数.函数oc将状态x映射到x接受的语言oc(x)。因为语言oc(x)可以被看作是x的可观察行为,所以函数oc被称为可观察性映射。现场总而言之,我们为我们的调查设定了以下场景1xεJ·库茨c2,c2,ε?zA(二)ArxXσ αJcoc2τJ·库茨(A)AXA(2A)A(rx)A(oc)A如果可达映射rx是满射的,则我们称(X,x,α)可达。如果可观测性映射oc是单射的,则我们称(X,c,α)为可观测的。如果rx是满射的,oc是内射的,那么我们称(X,x,c,α)(reachable and observable,or:)极小。对于一个给定的语言L∈2A,上面的图片有以下变化:1LεJCVZA2Aε?JC˛2其中下L实际上是L<$A<$的特征函数,并且其中同态h满足h=rL=oL和h(w)=Lw。因此,我们有h(v)=h(w)iu∈A这就是著名的迈希尔-内罗德等价关系 一个最小的-LJ. Rutten等人/理论计算机科学电子笔记298(2013)717|CQA.E/zHA/ker(h)2¸接受L的tomaton现在通过h的epi-mono因式分解获得:1LXεJcqzzizAε?JC2¸其中x=q<$ε且c=ε?我是阿吉这个最小自动机是唯一的直到同构,因为epi-mono因式分解是。由于A/ker(h)=im(h),它等于L即(2A<$,ε?)由L.在本节的结论中,我们观察到,在语言L中,是理性的这个事实是Kleene在有限自动机和理性语言之间的对应关系的一个版本[8,10]4方程与余方程我们将参考(2)的情况定 义 4.1 【 方 程 组 】 一 组 方 程 是 自 动 机 ( A, σ ) 上 的 互 模 拟 等 价 关 系E<$A<$×A<$我们定义(X,x,α)|= E-并说:指向自动机(X,x,α)满足E-,(X,x,α)|= E⇔ n(v,w)∈E,x v= x w因为n(v,w)∈E,x v= x w惠 E-100(rx)等价地,我们有(X,x,α)=E i,可达性映射rx因子通过A组/E组:1xε[ε]J一RxZXZ其中(指向自动机的)同态q和h由下式给出:q(w)=[w]h([w])=rx(w)我们定义(X,α)|= E-并说:自动机(X,α)满足E - by(X,α)|= E惠x:1 →X,(X,x,α)|= E惠函数x∈X,n(v,w)∈E,xv=xwQCL∗一18J. Rutten等人/理论计算机科学电子笔记298(2013)7Cε?注意,我们考虑方程组E,并且对于所有v,w,u∈A,(v,w)∈E意味着(vu,wu)∈ E,因为E-根据定义-是我们有时还考虑单个方程(v,w)∈A×A,并使用下面的简写:(X,x,α)|= v=w优惠 (X,x,α)|= E v=w其中Ev=w定义为包含(v,w)的A上我们还将使用变体,例如(X,x,α)|={v=w,t=u} ⇔ (X,x,α)|= v=w (X,x,α)|= t= u定义4.2[coequations]一组余方程是自动机(2A,τ)的子自动机D2A我们定义(X,c,α)|= D-并说:有色自动机(X,c,α)满足D -,(X,c,α)|= D优惠 x∈X,o c(x)∈D因为x∈X,o c(x)∈D⇔im(oc)等价地,我们有(X,c,α)|= D i = c因子的可观测性图,丁:Xh Doc2,ε?i2A迷你吧其中(有色自动机的)同态h和i由下式给出:h(x)=oc(x)i(L)=L我们定义(X,α)|= D-并且说:自动机(X,α)满足D - by(X,α)|= D惠函c:X→ 2,(X,c,α)|= D惠函数c:X→2,φx∈X,oc(x)∈DQ例4.3我们考虑由下图定义的自动机(Z,γ):一(Z,γ)=bB下面是一些等式的例子:(Z,x,γ)|={b = ε,ab = ε,aa = a}(Z,y,γ)|={a = ε,ba = ε,bb = b}x,,vy,,一J. Rutten等人/理论计算机科学电子笔记298(2013)719取这些集合的(互模拟等价)的交集,我们得到:(Z,γ)|={aa = a,bb = b,ab = b,ba = a}上面的方程组,或者更准确地说,由它生成的关于(A,σ)的互模拟等价关系,是由(Z,γ)满足的最大方程组。对于余方程的例子,我们考虑以下2个(所有4个可能的)(Z,γ)的彩色版本:一(Z,c,γ)=bB一(Z,d,γ)=bB(Thusc(x)= 1,c(y)= 0,d(x)= 0和d(y)= 1。C的可观测性映射并将这些自动机映射到B aim(oc)=BB aim(od)=B它遵循(Z,c,γ)|={(a<$b)<$,(a<$b)+}(Z,d,γ)|={(b<$a),(b<$a)+}Q5自由与余自由自动机设(X,α)是一个任意的自动机。我们展示如何构造一个自动机它对应于(X,α)满足的最大方程组并且,对偶地,我们构造了一个自动机,它对应于由(X,α)满足的最小余方程集为了记号的方便,我们假设X是有限的,但没有任何东西依赖于这个假设。定义5.1 [自由自动机,Eq(X,α)]设X ={x1,.,xn}是有限自动机(X,α)的状态集。我们分两步定义一个指向的自由自动机(X,α),如下所示:(i) 首先,我们取n点自动机(X,xi,α)的乘积,该自动机是通过让初始元素xi在X上的范围而获得的。 这就产生了一个点自动机(X,x<$,α<$),其中hX=Xxx:1→X(其中Xx=X),其中x<$=(x1, . ,xn),且其中α<$:<$X→(<$X)A定义为:α<$(y1, . ,yn)(a)=((y1)a, . . . 、(yn)a)x,,vy,,一x,,vy,,一(a、b)J一z),(a、b)+(b、a)+)一z_J,(ba)20J. Rutten等人/理论计算机科学电子笔记298(2013)7Σ¸(ii) 接下来,我们定义(free(X,α),x<$,α<$)byfree(X,α)=im(rx<$),其中rx<$是(x,x<$,α<$)的面积映射1x¯εx<$Jcrzz我在NAfree(X,α)rx<$_X此外,我们定义了以下方程组Eq(X,α)=ker(r)其中r是(free(X,α),x<$,α<$)的区域映射。Q注意free(X,α)=A/Eq(X,α)定义5.2 [cofree automaton,coEq(X,α)]设X ={x1,.,xn}是有限自动机(X,α)的状态集。我们分两步定义一个有色自动机cofree(X,α),如下所示:(i) 首先,我们取2n色自动机(X,c,α)的余积,它是通过让c在所有色函数的集合X→2上取值而得到的。这就产生了 一个 有色自动机(X,c,α),X=Xcc:X→2(其中Xc=X),且其中c和α定义为一个n t-wise。(ii) 下一个we定义(cofree(X,α),[c],[α])ycofree(X,α)=<$X/ker(oc),其中oc是(αX,cX,αX)的observability映射cnXqconfree(X,α)oc[c]2,ε?o2一个人其中[c]和[α]分别是c和α到等价类的扩张.此外,我们定义coEq(X,α)=im(o)J. Rutten等人/理论计算机科学电子笔记298(2013)721其中,o是(cofree(X,α),[c≠ 0],[α])的obser v a bilit y映射。Q注意cofree(X,α)=coEq(X,α)22J. Rutten等人/理论计算机科学电子笔记298(2013)7¸X1 ,zy_1,,一¸X3 ,zy_3,,一拉瓜定理5.3集合Eq(X,α)是由(X,α)满足的最大方程集合。集合coEq(X,α)是由(X,α)满足的最小余方程集合。Q例5.4[例4.3continued]我们考虑前面的例子一(Z,γ)=bB(Z,x,γ)和(Z,y,γ)的乘积是:(Z,(x,y),γ<$)=B取im(r(x,y))得到从(x,y)可达的部分:一 J(y,y)你好,(free(Z,γ),(x,y),γ<$)=(x,y) abJb(x≠,x),,B集合Eq(Z,γ)被定义为ker(r(x,y)),并且由(由下式生成的(A,σ方程(Z,γ)={aa=a,bb=b,ab=b,ba=a}这是(Z,γ)满足的最大方程组。接下来我们转向余方程。 (Z,γ)的所有4种颜色版本的余积是a一(Z,c,γ)=b bbBa aB bx,,vy,,一一一J(y),y),一你好,(x,y)一B(y,x)JB(x,x),,,¸X2 ,zy_2,,一¸X4 ,zy_4,,一J. Rutten等人/理论计算机科学电子笔记298(2013)723B b24J. Rutten等人/理论计算机科学电子笔记298(2013)7A. %roc(x1)oc(y1)oc(x2)oc(y2)oc(x3)oc(y3)oc(x4)oc(y4)∅(a<$b)A Ac:Z→2A的可观测性映射由下式给出:计算商ZerZ/ker(oc)得到:(cofree(Z,γ),[c],[γ])=a,bb aJ{x1,y1}Ja{x2},zJ{y2}Ba,bb aB这个自动机在可达映射o:cofree(Z,γ)→2A下的像是coEq(Z,γ)=a,bbaCTBa,bba(三)(b、a)+)一z_J,(ba)B这是(Z,γ)满足的最小余方程组。Q总结本节,对于每个自动机(X,α),我们得到了(2)的以下精化:1xεx<$C[c]2,ε?J·库茨vArfree(X,α)σα¯JcX轴αJCco自由(X,α)[中文]JCO2OτJC(A)Afree(X,α)AX<$Acofree(X,α)A(2<$A<$)A其中x的范围涵盖X的元素,c的范围涵盖X的所有可能的着色。自由自动机和余自由自动机表示由(X,α)满足的最大方程组和最小余方程组:Eq(X,α)=ker(r)coEq(X,α)=im(o)注意,自由自动机和上自由自动机是为自动机(X,α)构造J{x4,y4}Ja{x3},zJ{y3}∅(a、b)J一z_),(a、b)+J. Rutten等人/理论计算机科学电子笔记298(2013)725没有重点,没有色彩。 最后,让我们再次提到,上面的公式很容易推广到无穷大X。6变种与余变种我们通过方程和余方程来定义簇和余簇,首先是自动机,其次是语言。定义6.1[自动机的种类]对于每一个方程组E,我们定义Variety VEbyV E={(X,α)|(X,α)|{\fn方正粗倩简体\fs12\b1\bord1\shad1\3cH2F2F2F}Q定义6.2[自动机的余种]对于每一个余方程组D,我们定义余种CD为C D={(X,α)|(X,α)|{\fn黑体\fs19\bord1\shad1\1cHD8AFAF\4cHC08000\b0}Q每一种自动机都定义了一组语言,我们将再次称之为变种。对偶地,自动机的每一个余种都定义了一组语言,我们再次称之为余种。定义6.3[语言的多样性和共多样性]设VE是一个自体的多样性。我们定义语言L(VE)的多样性,L(V E)={L∈ 2 A<$|L<$∈V E}(其中,L是由L生成的(2A,τ)的子自动机)。对偶地,设CD是自动机的余变种。我们定义语言L(CD)的共变体为:L(C D)={L∈ 2 A<$|L<$∈C D}Q命题6.4每个簇V E在子自动机、同态像和乘积的形成下是封闭的。Q命题6.5每一个余簇C D在子自映射、同态象和余积的形成下是闭的。Q命题6.6一个同变种C D一般不在乘积下封闭。证据我们给出了一个在乘积下不封闭的共变种的例子。我们回想一下例5.4中的自动机,一(Z,γ)=bBx,,vy,,一26J. Rutten等人/理论计算机科学电子笔记298(2013)7一一J(y),y),一你好,(x,y)一B(y,x)JB(x,x),,,c((x,y))c((y,y))c((x,x))c((y,x))0110oc((x,y))oc((y,y))oc((x,x))oc((y,x))A+A<$A<$A +我们看到(Z,γ)|= D,其中D = coEq(Z,γ)如(3)中。(Z,γ)与自身的乘积为:(Z2,γ<$)=B我们定义一个着色c:Z2→2,这种着色c导致可观测性映射oc:Z2→2A,由下式给出:因为A+/∈D,自动机(Z2,γ<$)|=D. ThusC D未在产品下关闭。Q推论6.7不是每一个共变种C D也是一个变种。Q下面是(余)方程和(余变种)的一些基本性质。命题6.8对于每一组方程E<$A<$×A<$,L(VE)={L∈2 A<$|<$(v,w)∈E<$,Lv=Lw}其中E.Q定理6.9(关于方程与簇)设E <$A<$×A<$是一组方程.以下语句是等效的:0. E是一个同余1. E= Eq(X,α)对于某个自动机(X,α)2。(A/E,[σ])|= E3 .第三章。Eq(A/E,[σ])=E(with 如(2)中的σ)。此外,上述任何一项都意味着:四、L(V E)={L∈ 2 A<$|<$(v,w)∈E,Lv= Lw}.Q定理6.10(关于余方程与余簇)设D∈2A∈是余方程集.以下语句是等效的:
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功