没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记122(2005)193-210www.elsevier.com/locate/entcs把数据结构当作游戏AndreaSchalk1和Jos'eJuanPalacios-Perez2曼彻斯特大学计算机科学系联合王国摘要Curien的一个结果表明,可以将filiform具体数据结构视为游戏。我们扩展的想法,以涵盖所有稳定的具体数据结构。这就需要一个具有位置等价关系的博弈论。我们提出了一个忠实的函子从具体的数据结构的类别,这类新的游戏,允许游戏一样的阅读前者。这是可能的限制到这些游戏的一个carbohydrate封闭的子类,其中的功能空间不分解和产品是由通常的张量积结构。这些博弈和图博弈之间有着密切的联系。关键词:线性逻辑,游戏,具体数据结构,顺序计算具体的数据结构是由Kahn和Plotkin [9]作为计算域引入的。在某些具体的数据结构之间有着密切的联系,即那些在单元之间具有线性依赖性的这一结果在[4]中得到了证实。本文的主要工作是将这一结果推广到非线性数据结构。然而,我们不能将其扩展到所有具体的数据结构,而必须将自己限制在稳定的情况下。我们的结果需要引入一个新的游戏类别。在这里,博弈中的位置可以被识别,这限制了可能策略的数量,类似于图博弈的无冲突条件。我们定义了一个函子,从稳定的具体数据结构的范畴到这个新的游戏范畴。通过刻画它的形象,我们展示了后者的一个子类,这是相当于前者。1电子邮件:A. cs.man.ac.uk2电子邮件:palacioj@cs.man.ac.uk1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2004.06.058194A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193|∧∈−→1背景记法。如果A是B的一个子集,r是字母表B上的一个词,那么我们把从r中去掉所有不在A中的字母后出现的词写成rA。给定相同字母表上的单词r,rJ,我们将其写成rrJ,连接,r rJ为它们的最大联合前缀,如果r是rJ的前缀,写rrJ. 我们将连接符号扩展到符号集,并使用()表示Kleene星。给定一个字母表上的单词集合S,我们使用pre(S)作为S的前缀闭包。我们允许自己把A和B看作它们的和A+B的子集。在这可能引起混淆的地方(例如在和A+A中),我们使用inl和inr注入。1.1游戏我们描述一个简单的游戏类别。定义1.1一个博弈A包括:• 两个不相交的集合AP(玩家或P-移动)和AO(对手或O-移动);• pre((AO AP))语言的一个前缀闭子集pos(A)(博弈树)。因此,博弈A中的位置是属于博弈树的pre((AO AP))中的一个词,也就是pos(A)的一个元素一个位置是一个P-位置,如果它的最后一步是P-移动,否则是O-位置。换句话说,在pos(A)语言中,P-位置是偶数长度的单词,而O-位置是奇数长度的单词。我们用posP(A)来表示所有P-位置的集合,posO(A)也是如此。集合pos(A)可以很容易地被看作是一棵树,它的边被标记为移动,它的节点对应于位置,也就是pos(A)的元素树的“初始位置”或根由空词给出。对于r,rJpos(A)我们有时写rrJ如果有一个字母a使得rJ=ra。游戏A是pos(A)中的一个单词(或者是从词根到游戏树)。定义1.2博弈A的策略(对于参与者)是pos(A)的前缀封闭子语言α,具有以下性质:• 若r∈pos(A)是O-位置,ra,RAJ是α中的两个位置,则a=AJ(this被称为确定性(determinacy);• 如果r∈pos(A)是α中P-位置,则所有ra∈pos(A)也在α中。我们有时写α:A如果α是A的策略。如果我们考虑pos(A)A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193195|◦作为一个博弈树,那么策略α一定是一个子树。 一出符合A上的策略α是α中的词定义1.3两个博弈的线性函数空间AB具有• 移动集合(AB)O=AP+BO,(AB)P=AO+BP,以及• 博弈树位置(AB)={t∈pre(AB)O(A)B)P)|不|A∈ pos(A),不|B∈ pos(B)}。在我们的博弈范畴中,从A到B的(线性)态射通常是AB上的策略。我们解决了合成的问题。 让:A )B和C:B )C. 我们定义了一个符合和的联合序列,它是字母表AP+AO+BP+BO+CP+CO上的一个词w,使得的• W|A+B是一个符合A + B的游戏,• W|B+C是一部符合《圣经》的戏剧。我们将复合材料定义为ζ◦ξ={w|A+C|这是一个连接序列,在一个CC或D中,具有H和H}。很容易证明,如果t是π π中的一个位置,则存在唯一的与π和π一致的极小联合序列,比如w,其中wA+C=t。此外,如果t∈tJ,并且w和wJ是各自的最小联合序列,则w∈wJ。的在博弈A上的同一性是由“模仿”策略给出的这种组合也可以通过对集合和关系的范畴使用忠实函子来描述为关系组合,参见[6]。定义1.4两个博弈的张量积AB有• 移动集合(A<$B)O=AO+BO,(A<$B)P=AP+BP,以及• 博弈树pos(A <$B)={t ∈ pre(A <$B)O(A <$B)P)<$)|不|A∈ pos(A),不|B∈ pos(B)}。定义1.5两个博弈A和B的乘积A×B有• 移动集合(A×B)O=AO+BO和(A×B)P=AP+BP;• 位置pos(A+B)=pos(A)→pos(B)。终端游戏1是没有移动的游戏。这定义了一个著名的对称monoidal闭范畴Gaml。我们可以在[8]的意义下定义一个线性指数余子,使得所得的Kleisli范畴Gam是carnival闭的。线性指数是由于196A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193联系我们[4]见《易经更进一步,Gaml忠实地嵌入Gam。1.2具体数据结构具体的数据结构是由Kahn和Plotkin [9]作为一种特殊的计算域引入的。它们的预期用途是作为编程语言的语义宇宙。从那时起,他们已经习惯于以多种方式理解顺序性。可以在[2,3]中找到帐户。定义1.6一个具体的数据结构(cds)R=(C,V,ev(R),v)有• (单元格的)集合C• 与C不相交的(值的)集合V;• (事件的)关系ev(R)<$C×V;• 有限组事件和细胞之间的关系(使能关系)。我们假定,在[2]的意义上,使能关系是有充分根据的,而定义1.7具体数据结构R的状态ρ是具有以下属性的事件集合:• 如果(c,v)和(c,vJ)都在ρ中,则v=vJ(这称为相容性)。• 对于所有的ρ中的(c,v),有(c1,v1,),. (c n,v n)=(c,v)in ρ使得对所有1 i n,(c1,v1),.,(c i−1,v i−1)包含c i的启用(这称为安全性)。我们通常使用st(R)来表示R的所有状态的集合,而stf(R)表示R的所有有限状态的集合。我们有时写ρ:R来表示ρ是R的一个态。给定一组事件ρ,我们说一个单元格c在ρ中被使能但未被填充,只要ρ包含c的使能且c未在ρ中发生。当我们将cdss转换为游戏时,我们希望将单元格视为对手,并将值视为玩家移动。特别地,我们希望建立满足安全性和一致性条件的事件序列的读数,在pre((CV))中是一个字符串另一方面,给定一个字符串r∈pre((CV)<$),我们可以得到C×V的一个子集,我们称之为[r<$],通过设置[r∈ {(c,v)∈ C × V |rJ∈(CV)rJcv r}。在适当的情况下,[r]将是一组事件,甚至是一种状态。cdsR的游程是pre((CV))中的一个词r,使得对于RA. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193197[2014-05-23][• [r]是一个国家;• 如果rJ= rJJc具有奇数长度,则c被使能但不填充在[rJJ]中。R的状态ρ的游程是R的游程r,使得Rρ. 我们可以恢复从其所有运行的集合中提取状态。我们可以把使能关系看作是规定某些事件必须在其他事件发生之前发生--我们得到了一些关于状态的可能序列化的信息。一般来说,将状态序列化的方法有很多,也就是说,对于给定的状态ρ,将有许多游程r,使得r=ρ。这样一个r的某些子串可以自由互换,因为在一个子串中发生的任何事情都不依赖于在另一个子串中发生的任何事情当我们把cdss转化为博弈,把状态转化为策略时,我们是按照这样的序列化来做的。定义1.8我们说cds是稳定的,如果对于所有使能x<$c,xJ<$c,使得存在一个同时包含x和xJ的状态,存在xJJ<$x<$xJ,xJJ<$c。我们认为,假设所有的CDS都是稳定的,从现在开始将不再另行通知。定义1.9两个cdssR =(C,V,ev(R),n)和S=(D,W,ev(S),n)的函数空间R∈S• 细胞:stf(R)×D;• 值:C+W;• 事件:所有对· ((ρ,d),c)使得c被使能但不填充在ρ中,· ((ρ,d),w)使得(d,w)是S中的事件;• 启用:所有实例((ρ,d),c)<$(ρJ,d)使得存在v∈V,其中ρJ=ρ <${(c,v)},且((ρ1,d1),w1),... ,((ρ n,d n),w n)<$(ρ,d)使得ρ=ρ1<$··<$ρ n和(d1,w1),.,(dn,wn)在S.cdss从R =(C,V,E,)到S =(D,W,F,)的态射是函数空间的一个状态。我们可以把这种态射看作是一组指令,它允许我们在左手博弈中使用信息(来自R的单元格中的值)来填充右手博弈中的单元格。198A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193⇒J⇒⇒φ⎩⎨⇒定义合成是不平凡的。我们在这里给一个简短的说明,这是从[2]。给定RS中的一个状态φ,可以定义一个偏函数gφ:stfR×D ~C+W,这是从R S的单元到相同cds的值的部分函数这是通过设置g φ(ρ,d)= z i <$$>ρJ <$ρ其中((ρJ,d),z)∈φ且((ρ,d),z)是R<$S中的事件.这样的gφ被称为给定g:stfR×D ~C+W存在φ:RS,其中g=gφ当且仅当以下成立:• 如果g(ρ,d)=z,则((ρ,d),z)是R∈S中的事件。• 若g(ρ,d)=z且存在ρJ<$ρ使得((ρJ,d),z)是R<$S则g(ρ,d)=z.• Ifg(ρ,d)被定义为 使d在{(dJ,w)}中成立|g(ρ, DJ)=w},且若dj∈ρj,则d也可在{(DJ,w)}中定义|g(ρJ,dJ)=w},则ng(ρJ,d)也被定义。我们可以从gφ得到φφ={((ρ,d),x)|g φ(ρ,d)= x且ρ是具有该性质的极小值}。为了构造抽象算法,我们必须注意,φ:R<$S定义函数st(φ):st(R))st(S),通过设置st(φ)(ρ)={(d,w)∈ ev(S)|你好((ρJ,d),w)∈ φ}.给定两个状态φ:R S和φ:S T,其复合的标准定义是给出相应的抽象算法,即:(g)◦ g)(ρ,e)=xg(st(φ)(ρ),e)=xcg φ(st(φ)(ρ),e)= d和g φ(ρ,d)=c.cdsR的身份描述为:gidR(ρ,c)=<$v(c,v)∈ρc(c,v)/∈ ρ.还有另一种对构图的定义,它更像是一种游戏。假设我们有一个态射φ:R)S,它是R S的一个态φ。下面的引理是[2]中所含材料的一个推论。A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193199ρ⇒1∈1n1−1n1−1n11111nm−1nm−1nmJ引理1.10对于形式为R S的cds,下列成立。称R的某个φ的游程为正规的,如果它具有以下形式:(ρ1,d1)c1···(ρ1,d1)c1(ρ1,d1)w1(ρ2,d2)c2···(ρm,dm)cm···(ρm,dm)cm(ρm,dn)wm其中最后一个元素是可选的,使得i,ji是R的状态。然后φ={((ρ,d),x)∈φ|以(ρ,d)x结尾的φ的正态游程}。换句话说,在正常运行中,一旦D中的一个单元格d被玩过,我们就不能提到D中的其他单元格,直到d被填满。此外,我们只允许运行,这是一致的,在他们的要求,从R的信息。φ的正常运行包含大量信息,其中一些我们可以丢弃。给定一个正常运行,我们想在pre((D(CV)W))中构建一个字符串,我们需要在下面将φ解释为一个策略。 φ的经济运行:R S是pre((D(CV)W))中的一个词,它由φ的正常运行递归生成,如下所示:• 长度为0的游程。 对于空运行,取空字符串。• 长度为n + 1的游程。设(ρ1,d1)x1···(ρn,dn)xn(ρn+1,dn+1)xn+1是φ的一个正规游程,r是给定游程到(ρn,dn)xn的经济游程.我们根据xn是C的元素还是W· xn∈C. 在这种情况下,dn=dn+1和ρn+1=ρn<${(xn,v)},对于某个v∈V,取rvxn+1。· xn∈W。在这种情况下,dn和dn+1是不同的,我们取rdn+1xn+1。显然,从正常运行到相应的经济运行并没有真正丢失任何信息,我们可以很容易地从后者重建前者。然而,我们需要剥离更多的信息。请注意,根据正常运行的定义,如果一个经济运行不止一次包含单元格c,那么它的后继值,即来自V的值,在所有情况下都必须相同。给定一个经济运行r,我们通过去除重复的对cvev(R)来获得相应的基本运行。 一般来说,不可能从相应的基本形式中重建一个经济运行。然而,把态射的基本游程放在一起就足以刻画它。例1.11考虑cdsR,它有一个初始使能的单元c和一个值v,以及cdsS,它有两个初始使能的单元d和DJ,这两个单元都可以用值w填充。然后φ={((d,d),c),(({(c,v)},d),w),((d,dJ),c),(({(c,v)},dJ),w)}200A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193⇒◦的|♩的|♩是R∈S的一个状态,其最大正规游程为(n,d)c({(c,v)},d)w(n,dJ)c({(c,v)},dJ)w和(n,d,J)c({(c,v)},d,J)w(n,d)c({(c,v)},d)w,最 大 经 济 运 行 dcvwdJcvw 和 DJcvwdcvw 以 及 最 大 基 本 运 行 dcvwdJw 和DJcvwdw。这两个运行一起允许我们推断,d和DJ都需要填充单元格c才能被赋值。请注意,在R上的身份的基本运行非常令人想起模仿策略。引理1.12 R S的一个态φ由它的基本游程集唯一确定。证明(略)给定一个R S中的事件((ρ,d),x),我们必须决定它是否在φ中。考虑所有基本游程t,它包含d作为它们从D开始的最后一个符号,x作为它们的最后一个字母,并且它使得tC+V包含在ρ中。如果有这样一个运行,它是最小的所有这些在prefix顺序与性质,tC+V等于ρ,则事件属于φ,否则 但事实并非如此。Qφ和φ的联合基本游程是(C+V+D+W+E+X)中的字z,使得• z|C+V+D+W是φ的基本游程,• z|D+W+E+X是一个基本的连读。命题1.13基本游程的集合是{z|C+V+E+X|zφ和φ的联合基本行程}。证明(草图)不难证明上述基本游程集合包含在φ φ的基本游程集合中-证明是通过形成联合基本游程的方式进行另一个包含让人想起Gam中的组合可以被描述为关系组合的Q定义1.14两个cdssR =(C,V,E,N)和S=(D,W,F,N)的乘积R×S有• 细胞:C+D;• 值:V+W;• 事件:evR+ev(S)<$(C×V)+(D×W)<$(C+D)×(V+W);• enablings:来自R的所有enablings和来自S的所有enablings。终端cds 1有空的单元格和值集。A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193201定理1.15范畴CDS是具有上述结构的Carnival闭范畴。1.3游戏和filiform cdss有一些非常特殊的具体数据结构与游戏密切相关。它们具有使能关系具有非常受限的形式的属性;因此,包含给定事件的最小状态具有唯一的序列化。定义1.16我们说cds是filiform,如果使能关系的所有实例都引用至多有一个元素的事件集。我们把这种具体的数据结构称为fcds。设FCDS是CDS的全子范畴,其对象是稳定的文件形具体数据结构。由于CDS中的函数空间和乘积保持了Filiform性质,FCDS已关闭。对于cds,我们定义一个博弈,其对手移动是R的单元格,其玩家移动是值。然后,一个游戏应该对应于某种类型的运行,即在每个阶段,下一个单元第一次被启用。对于一个Filiform cdsR,一个态ρ精确地由它的这种游程给出。对于cdsR,让TR成为具有• 移动集合(T R)O=C和(T R)P=V;• ·空词在pos(T R)中。· 给定r∈posP(T R),对于C中的c,rc∈posO(T R)当且仅当c是使能的,但在[r]中没有填充如果rJ<$r,则在[rJ <$]中启用c意味着r=rJ。· 给定r∈posO(T R),对于v∈ V,rv∈pos(T R)当且仅当对某个c∈C,r=rjc且(c,v)是事件;那么R上的状态恰好对应于T R上的策略:ρ,让相应的策略由下式给出:{r ∈ pos(T R)|[r∈ ρ}。这有助于建立以下结果。命题1.17范畴FCDS和Gam是等价的。在[4]中,作者描述了一类序列数据结构,它是游戏和FCDS之间的混合体,但很明显,他的类别相当于我们的Gam和FCDS。这是主要目的202A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193J本文将这一思想推广到所有稳定的CDSS。很明显,游戏和一般的cdss之间的匹配不能指望那么接近。它可以通过考虑一些位置被识别的游戏来改进。2具有已识别位置的人们已经注意到,在博弈中,人们可能只想考虑到某种等价关系的位置,这可能是有原因的。图游戏[8]是这种方法的一个有点极端的版本,我们知道至少有两个其他的游戏,通过Melli'es[10]和Houston[5]。她试图保持理论尽可能简单,同时仍然使其足够普遍,以适用于其他情况。我们的动机来自于试图将所有的cdss都视为游戏,也就是说,不限于filiform的情况。很明显,我们必须想出另一种从CD构建游戏的方法。对于cds,我们要定义一个包含所有可能的cds运行的游戏。我们再次将单元格转换为对手移动,将值转换为玩家移动。 对于filiform cdss,我们可以捕获所有的结构,如果我们一个单元格,定义从给定位置的有效移动,当且仅当该单元格在该位置被启用但未填充,并且该单元格未被该位置的任何前缀启用。然而对于一般的cdss,我们必须选择一种不同的方式来形成有效的播放我们必须放弃单元格在较早位置未被启用的条件。给定一个cdsR,设FR为博弈,其中:• 移动集合(FR)O=C和(FR)P=V;• ·空词在pos(FR)中。· 给定r∈posP(FR),对于C中的c,rc∈posO(FR)当且仅当c在[ r]中被使能但未被填充。· 给定r∈posO(FR),对于V中的v,rv∈pos(FR)当且仅当对某个c∈C,r=rjc且(c,v)是事件;备注。FR的打法和R的跑位之间存在一一对应关系,而在TR的Filiform情况下,它是在打法和限制跑位之间。显然,一般来说,FR上的策略比R上的状态多。例2.1考虑cdsR,其中C={c,cJ,cJJ},V={v},单元格和值的所有可能组合都是事件,并且其中c和c由空集使能,而(c,v),(cJ,v)∈cJJ。这是最小的非Filiform CD。A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193203J∼vcJJvFRvcJJvCJCV VCCJCDS有四种状态,而FR有九种策略。我们的目标是在接下来的内容中删除至少一些不受欢迎的策略。R的状态和FR上的策略之间不匹配的一个原因一个策略包含状态的序列化,一般来说,一个状态可能有很多序列化。此外,一个策略可能愿意执行其中一些序列化,而不是其他序列化。这个问题不会出现在fcdss中,因为每个包含某个事件的最小状态都有一个序列化。减少策略数量的一种方法是识别FR中对应于同一潜在状态的位置,然后要求所有策略都在该等价关系中表现良好我们想确定位置r,rJ∈posP(FR)当且仅当[r]=[r],这相当于说,在r和rJ中执行的由对手移动和随后的玩家移动组成的对是相同的,它们只是以不同的顺序发生。证明rc,RJcJ∈posO(FR)当且仅当r<$RJ且c=c.定义2.2一个博弈-博弈(A,A)是一个具有等价关系的博弈A满足下列条件的A• P-位置只能与其他P-位置相关,因此类似的情况也适用于O-位置.• 如果r和RJ是两个与位置相关的位置,则如果ra∈pos(A),则RJa∈pos(A)且ra∈RJa。• 没有一个位置与它的适当前缀之一相关。• 如果ra和raJ是相关的,那么a=aJ。注意,如果r和rJ是两个相关的位置,则以r为根的博弈的完整子树与以rJ为根的博弈的子树相同,包括n关系。定义2.3(A,B,A)和(B,B)的线性函数空间是(A204A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193∼∼∼≤| ∼ ||≺|||其中对于A的位置t和tJ,B我们设置ttJ当且仅当(t|AtJ|A和t|BtJB)。一个类似的定义被用来定义一个张量积的双对策。更有趣的是,我们应该考虑什么样的战略概念-游戏?显然,如果我们确定头寸的动机是有意义的,那么至少我们只想允许A上的α策略,如果r rJ是α中的O-位置,则α有r的答案当且仅当它有rJ的答案,并且两个结果位置再次等价。在这种情况下,一个更强的版本是要求ra∈α当且仅当rJa∈α。但事实证明,这两个都不够强大,以确保所产生的战略组成。见[5]在一个稍微不同的设置中讨论这个问题在我们给出定义之前,我们引入以下符号。对于一个博弈中的两个位置r,r,J,我们写如果r≤rJ ,并且只有当r存在时,r才具有hr_j_r_J。换句话说,r是一种打法,一旦增加了更多的移动,它就可以变得与rJ再换一种说法,在通过确定相关位置而得到的无圈有向图中,存在一条路径从与r(的等价类)对应的节点到rJ(的等价类)。 如果r≤rJ但不是r <$rJ,我们写r<$rJ--换句话说,要从r到一个与rJ相关的策略,我们必须至少增加一步。如果A和B是两个博弈,那么我们可以从A和B上的关系确定AB上的关系,尽管有一个附带条件:例如,对于A中的位置t和tJ,B我们有t AtJA,t BtJB和所有这些是P-位置,那么唯一的方法是从就是在B中进一步移动。 然而,如果tA和tB都是P-位置,那么下一个动作必须发生在A,所以我们在与t j相关的事情上被引理2.4设t和tJ是A B中的两个位置。然后t≤ tJ当且仅当(t|A≤tJ|A)和(t|B≤tJ|B)和不是((t|AtJ|A,t|B(t,JB,所有位置)或(t|AtJ|A,t|B=JB,所有O-位置))。定义2.5(A,λ)上的α-策略α是A上的策略α,使得• 若r,RJ∈α是O-位置,且对某个P-移动a,ra∈α,则RJa∈α;A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193205◦||≤××◦⊗∼• 若r∈posO(A)和RJ∈posP(A)是α中的两个位置,且r <$RJ,则存在ra∈α使得ra≤RJ.身份显然是一种策略。为了证明双策略的合成,我们需要一个辅助结果。设A:B和B:B:C是两个双策略.引理2.6设t和tJ是矩阵中的两个位置,w和wJ分别是t和t j的唯一符合矩阵和矩阵的极小联合序列,则w|A+C= t,wJ|A+C= tJ。如果t=J,则w|BwJ|B.证明(草图)证明过程通过归纳W的构造进行。所以假设我们已经建立了长度为n的v w,使得v|A≤ wJ|A,v|B≤ wJ|B和v|C≤wJ|显然空序列具有这些性质。当我们到达v = w时,我们停止,所以假设v中至少有一个|AwJ|A和v|CwJ|C. 有四种情况下,可以出现时延长v一步,即(v|A,v|B,v|C)在•P(A)位置P(B)位置posP(C):下一步是C中的对手,调用it诺氏梭但是vcC wCwJ,从A或B• posP(A)×posP(B)×posO(C):下一步是W的答案|B+C,称之为d(从B或C)。 但不管是哪种vd|B+C≤wJ|B+C,因为它是a-策略,因此vd|B≤wJ|B和VD|C≤ wJ|C.• posP(A)×posO(B)×posO(C):这种情况是前一种情况的对偶 一个.• posO(A)×posO(B)×posO(C):这种情况与第一种情况是对偶的Q推论2.7设t和tJ是序列中的两个位置,w和wJ是各自的唯一联合序列。然后t≤tJ当且仅当w|AwJ|A和w|BwJ|B和w|CwCJ.命题2.8两个随机策略的合成是随机策略。证明(草图)第一个条件是通过使用联合序列的构建方式来显示的;这是一个简单的情况区分(添加到合成中现有位置的新移动可以来自源或目标),并使用合成策略满足该条件。第二个条件可以通过前面两个引理的应用来证明 Q很明显,(AB)C同构于A(BC),因此我们得到了一个对称的单态闭包。这是如何定义两个的乘积的方法。- 博弈,等价关系是这两种等价关系。终端对象只有一个位置,因此只有一个等价关系,将其转化为一个博弈。 我们206A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193∼∼∼∼−→可以给一个线性指数comonad的游戏,但因为我们没有使用它在这里,我们不包括一个定义。从Gaml到Gaml,存在着一个新的遗忘因子,它反映了范畴结构,并且是忠实的. 另一方面,如果我们一个具有平凡等价关系的对策,其中每一个位置只等价于它自己,那么我们得到一个满的和忠实的monoidal函子。然而,这两个函子并不构成一个附加函数。其原因是单位和合作单位的唯一候选者是模仿策略,但在加姆里生活的不是一个秘密的战略。建议2.9CategoryGaml与文献[7]中对群博弈GGam的分类是等价的。证明(草图)我们将-博弈A映射到图博弈,其位置是位置A的等价类,其中存在从[r]到[rJ]的移动。当且仅当存在a且ra∈rJ。很明显,我们应该做些什么,策略,主要的挑战是证明结果满足无冲突条件,但这从-策略的条件中显而易见。 在相反的方向上,将图博弈A映射到其移动形式为(rr j)的博弈,只要rRJ在A. 两个位置等价当且仅当如果他们的最后一步棋结束于A的同一位置这就是“树”[7]的函子,具有明显的等价关系。Q对于这个应用程序,我们将参考GGa中的工作,因为GGa中没有命名移动的概念我们的范畴与Melli`e描述扩展数据结构(edss)[10]有一点模糊的相似之处: -Game,把它读作eds,把P-位置的等价类作为扩展,其中这样的类实现了它的所有成员。因此,我们的竞争策略是实现所有扩展的策略。然而,Melli`e有一个更一般的态射概念,所以当我们得到一个函子时,联系并不紧密。此外,鉴于一个eds有没有明显的方式把它变成一个游戏。3Cdss作为游戏我们想把赋值F变成一个函子(CDS)Gam?。注意F(R×S)<$=FR<$FS且F1<$=I,将CDS中的产品映射到Ga中的产品。对于fcdss,我们在R上的状态和TR上的策略之间有很好的关系。如果我们看看一般cdss和F的情况,那么我们注意到,如果ρ是R的一个状态,那么我们可以从它导出FR上的一个π-策略Fρ。这个想法A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193207∼⇒∼×∼∼Fρ试图通过用适当的值填充ρ填充的所有单元格来形式上,对于FR的播放器r,r∈ Fρ当且仅当[r∈ ρ.然而,一般来说,FR的策略比R的状态多。其原因是,虽然在某些情况下,一个策略可能会准备用值v填充某个单元格c,但没有任何东西迫使它在任何可能的情况下这样做。特别是在例2.1中考虑策略pre{cvcJ,cJvc}。 这可能对应的唯一状态是ρ={(c,v),(cJ,v)},但用Fρ = pre{cvcJv,cJvcv}可以更好地解释。更一般地,考虑F(R×S)= FR<$FS。对于R × S上的某个状态τ,F(R×S)上由Fτ产生的唯一策略是形式Fρ<$Fσ,其中ρ:R和σ:S。我们已经定义了CDS对象上的作用,它仍然需要将Ditt映射扩展到函数F:CDS)Gaml. 一个ssum可以有一个态射φ:R)S,即R S的一个态φ。然后我们定义Fφ:FR)FS是φ的所有游程的集合。注意,我们可以把ρ:R读作一个态射ρ:1)R,它映射到Fρ:I=F1)F R,这对应于上面定义的Fρ:FR命题3.1这定义了一个忠实的函数F:CDS)Gaml.证明(草图)很容易证明φ的每一次运行确实是FRFS的一次博弈,并且不难证明这个集合定义了一个-策略。 对于函子性,所有的困难工作都由命题1.13完成,我们知道赋值是忠实的,由引理1.12。Q注意,我们可以通过使用对应于φ,gφ的抽象算法来归纳地描述Fφ。命题3.2以下内容在给定条件下是等价的:FRFS:• 存在φ:R<$S,其中φ=Fφ;• 存在一个抽象算法g:stfR D~C + W在下面的意义上定义f:设t是Fφ中的奇长字,设d是从D开始在t中出现的最后一个符号。 则g对t的唯一回答由g([t|C+V,d)(如果g在该点未定义,则也未定义);• φ通过后合成将FR的形式为Fρ的-策略映射到FS的形式为Fσ的-策略。这个条件是历史自由性的一个概括[1],在这个意义上,如果α:FR则如果α等于Fρ,对于某个ρ:R当且仅当它是无历史的。208A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193∼[2014-05-23]∈⎧⎪⎨(ρ,σ∪{(d,w)})gφ(ρ,d)=w·∈ ∼∼看到函子G:CDS)GGam的定义是很有启发性的,它是由命题2.9的等价组成的F。 对于cdsR,设GR是图博弈,其具有P-位置R的有限状态,和O-位置这样的状态ρ以及使能但未填充在ρ中的单元c。动作很明显。对于一个状态φ:RS,设Gφ为策略,定义为:Gφ(ρ,(σ,d))=((ρ,c),(σ,d))gφ(ρ,d)=c否则我就不客气了。G下的态射的像有很好的刻画,但我们在这里不给出它们,因为这需要介绍更多关于图博弈的材料我们对一个高斯图像进行了量化,其中CDS的图像是非高斯的。derF.为此,我们将的定义推广到任意博弈A的博弈r,[r∈ {(a,AJ)∈ AO× AP|. rJaaj r}。命题3.3给定一个-对策A,存在一个cdsR,其中FR=A当且仅当对于A的所有对策r,RJ• rarJaposO(A)意味着r是空串(每个O-移动在每次游戏中最多发生一次);• ·对于r,rJ∈posP(A),r<$rJ当且仅当[r<$=[rJ<$,对于ra,rJaJ posO(A),ra rJaJ当且仅当r rJ且a=aJ(two战术是等价的,如果它们包含相同的(O-移动,P-移动)可能以不同的顺序对,并适当处理尾随O-移动);• r<$rJ蕴涵r<$rj∈posP(A)(等价位置在O-移动处发散);•RAAJ∈posP(A),rJa∈posO(A)蕴涵rJaaJ∈posP(A)(如果P-移动aJ曾经是O-移动a的有效答案,那么这在任何地方都成立• ra∈posO(A),rJ∈posP(A),[r[rJ,a不出现在rJ中隐含rJa∈posO(A)(a被使能保持有效,直到它被应答);• ra,rJa ∈posO(A)和r <$rJ∈posP(A)蕴涵(r <$rJ)a ∈ posO(A)(稳定性).证明(草图)cdsR有单元格AO,值AP,事件all(a,aJ)∈AO×AP,使得存在r∈pos(A),其中raaJ∈pos(A),并使[r]的所有实例都成立,使得ra∈pos(A),并且对于所有rJ<$r,rJa/∈pos(A)。Q让CDSG成为一个由F的图像组成的图像。A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193209×⊗⊗⊗Theorem3. 4、CDSG模型是一种自流井模型,其等效于CDS。这有点令人惊讶,因为这是一个carnival封闭的游戏类别,它不是基于函数空间的分解-相反,函数空间是Gam?l的线性函数空间。和产品是这个范畴的张量积 看看为什么被识别的子范畴的张量积成为乘积。据预测,在Gaml中,例如πl:ABA是由复制猫策略给出的,它将A的右手副本复制到左手副本,反之亦然,游戏B永远不会开始。在CDSG算法中,e是在rF下的投影图像。 问题在于定义配对运算。但是在F的图像中,我们有一个对角线δ R:FR)FR FR(对角线R的图像)R R R在CDS中:给定δ R中的O位置t,我们计算它对所有三个分量的限制,以获得FR的三个策略r,rJ和rJJ,其中r是rJ和rJJ的交织,在最后加上或减去一个额外的移动。 如果在r中有一个额外的移动,我们复制它作为我们的答案t,否则有一个额外的移动到RJ或RJJ,我们复制它。请注意,这是唯一可能的,因为我们知道适当的移动是可用的在FR中,所以我们正在大量使用这种形式的游戏的特殊性质。对于Fφ:FRFS,F:FRFT我们设置Fφ,Fφ:FR )FSFT到FRδR)FR<$FFF φ<$F)<$FS<$F T,这就等于F<$φ,<$φ:FR)F(S×T)<$= F S<$ FT.请注意,为了在我们的carlington闭范畴中组合策略,我们可以只使用线性态射的组合,而不必通过某些Kleisli范畴。在某些方面,FR形式的对象的行为有点像类型的对象!A,但据我们所知,没有线性指数,这将允许我们写FR这样。结论和今后的工作我们已经建立了一个游戏的范畴,这是相当于具体的数据结构的范畴。这产生了一个描述的一个cardian封闭类别的游戏,这是不是克莱斯利类别的一些线性指数。对于这项工作来说,定义一类具有位置等价关系的额外结构的博弈是至关重要的。这一范畴等价于图游戏范畴,但它命名了移动,没有这些移动,就不能定义一个卡宾枪闭子范畴对于这个类别,我们有210A. Schalk,J.J.Palacios-Perez/Electron.注意Theor。Comput. Sci. 122(2005)193限制到游戏的一个非常特殊的性质和态射可以描述使用部分功能。具体的数据结构可以被看作是特殊的事件结构,我们在上面论证了一个状态中的一些事件是独立于其他事件的,一个原始的并发概念。一个有趣的问题是,这些游戏是否可以用来制造更多的电子硼酸盐
下载后可阅读完整内容,剩余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直接复制
信息提交成功