没有合适的资源?快使用搜索试试~ 我知道了~
›→−·⊥−·⊥理论计算机科学电子笔记122(2005)171-192www.elsevier.com/locate/entcs异步游戏3线性逻辑Paul-Andr'eMelli`esEquipePreuvesProgrammesSyst`emesCNRSettUniversit′eDenisDiderot Paris,France摘要从早期开始,确定性序列博弈语义就被限制在线性逻辑的线性或每一次试图将语义扩展到完全命题线性逻辑的尝试都与所谓的布拉斯问题(Blass problem)发生了碰撞,布拉斯问题(Blass problem)(误导性地)表明一类序列博弈不能同时是自对偶和卡拉斯问题。我们通过考虑(1)序贯博弈本质上是位置性的;(2)序贯博弈既承认内部位置,也承认外部位置,来规避这个问题。我们以这种方式构建了一个命题线性逻辑的序列博弈模型,它包含了无辜的竞技场博弈模型的两个变体:好括号和非好括号的。关键词:博弈语义,线性逻辑,范畴模型。前言本文不是简单地介绍我们的命题线性逻辑的无辜模型。它还详细解释了使其存在的概念阶段。 我们希望这份报告能让有明确想法的听众满意。本文件组织了六个部分。我们开始回顾和乔亚尔我们证明了范畴Y没有二元积(第2节)。这一事实是众所周知的,但证据并没有出现在任何地方的全部细节。然后,我们把Blass问题归结为这样一个事实,即线性连续单子A( (A))在Conway对策上是强的但不是可交换的。最后,在异步博弈的速成课程(第4节)之后,我们构造了一个等价于恒等函子的线性连续单子,1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2004.06.057172P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171允许在游戏中使用内部位置这就绕过了布拉斯问题,并定义了一个线性逻辑模型(第5节)。我们得出结论(第6节)。1攻略:康威小游戏两个星期前,和R'EJOY都是由JOH。C在超现实数的道路上,他可以构建一个范畴Y,康威游戏作为对象,获胜策略作为态射,由序列相互作用组成这个结构 出 现 在 一 篇 7 页 的 文 章 中 , 用 法 语 写 的 , 并 于 1977 年 发 表 在GazettedesSciencesMath'ematiquesduQu'ebec [7]。由于这是一个极端的困难,以获得一个合作的公报,今天,我们发现有用的recallbelow和r'eJoyal的constructi on的在解释这个范畴之前,我们有必要简单地讨论一下是什么让Y范畴在今天如此有趣。至少有两个原因。从历史上看,它是证明理论和编程语言的游戏语义学的先驱。从概念上讲,它是一个自对偶范畴的序贯博弈。我们对最后一点特别感兴趣。今天所考虑的博弈范畴一般都是对称的monoidal封闭的,有张量积(注:)和monoidal封闭(注:)。除了少数例外,它们不是自对偶的。相反,范畴Y是n-自治的,也就是说,是对称monoidal闭的,其对偶对象n构成典范态射:A−→((A))在范畴Y中的同构,对于每个康威对策A。由于我们正在寻找完全命题线性逻辑的博弈模型,并且由于线性逻辑是基于证明和反证明之间的对偶性,因此我们发现更仔细地研究范畴Y是非常有益的。 为了读者这种选择也是在最近的帐户(金钱)游戏的sy和r'e乔y a l[8]。这可能不是最好的介绍,但它澄清了与我们自己的线性逻辑博弈论模型的联系,在第5节中给出。康威游戏Conway对策是一个有向图(V,E,λ),由一个顶点集V、一个边集EV×V和一个函数λ组成:E−→{−1, +1}将极性−1或+1关联到图形的每条边 顶点称为博弈的位置,边称为博弈的移动。直觉上,当λ(m)=+1时,参与者会走一步m∈E,当λ(m)= −1时,对手会走一步m ∈ E。在图论中,当(x,y)∈E时,我们写x → y,P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171173以及调用路径位置s =(x0,x1,..., 其中对于每个i∈{0,. ,k-1}。在这样的例子中,我们写s:x0−−→→xk来表示s是从位置x0到位置x k的路径。为了成为康威博弈,图(V,E,λ)需要验证两个额外的性质:• 图是有根的:存在一个称为博弈根的位置x ∈ V,使得对于每隔一个位置x∈V,都存在从根开始在位置x:x1→x2 →x3··· →xk →x,• 这个图是有根据的:每个位置→x1 →x2 →x3→···从根开始是有限的。路径s =(x0,x1,...,x k,x k+1)称为交替,当:i ∈ {1,.,k − 1}, λ(xi→xi+1)= −λ(xi−1→xi).一个游戏被定义为一个paths:从root开始的n−−→xs。康威对策A的局集记为PA.制胜战略。康威博弈(E,V,λ)的策略σ被定义为一组交替策略,使得对于每个位置x,y,z,z1,z2:(i) 空场()是σ的元素,(ii) 每一局s∈σ都以对手的移动开始,以玩家的移动结束,(iii) 对于每一个平面:x−−→→x,对于每一个Opponent移动x→y和Player移动y→z,S s<$−−→→x→y→z∈σ<$<$−→x∈σ,(iv) 对于每一个平面s:n−−→→x,对于每一个Oponent移动x→y和Player移动y→z1和y→z2,S s<$−−→→x→y→z1∈σ和<$−−→→x→y→z2∈σ <$z1=z2。因此,一个策略是一组在偶数长度前缀(第3章)和确定性(第4章)下封闭的策略一个策略σ被称为获胜,当对于每个平面s:−−→→x元素n到σ和deveyOpponent元素x→y,其ex是ts174P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171如果y→v,S⊗⊗一⊗ ◦⊗⊗⊗⊗−→AA甚至一个位置z和一个参与者移动y→z,−−→→x→y→z是策略σ的元素。 注意,根据决定论,在这种情况下,位置z是唯一的。我们写σ:A表示σ是A的获胜策略。对偶和张量积。康威博弈A =(V,E,λ)的对偶A是康威博弈A=(V,E,−λ)通过反转移动的极性而得到的。两个康威博弈A和B的张量积A B是Conway游戏定义如下:• 它的位置是博弈A的位置x的对(x,y),记为xy和博弈B的位置y• 它从位置x到y的移动有两种:如果x→u,• 移动xy→uy记为(x→u)y,并且具有博弈A中移动x→u的极性;移动xy→xv记为x(y→v),并且具有博弈B中移动y→v的极性。两个Conway对策A和B的张量积A ∈ B的每一个对策s都可以投影到一个对策s上|A∈P A,对于一个博弈s|B∈P B。 Conway游戏1 =(,,λ)有一个空集的位置和移动。Conway游戏的Y类。 范畴Y以Conway对策为对象,以A → B的获胜策略为态射A → B。身份策略idA:A将一个组件A中接收到的每个移动复制到另一个组件。 两个策略σ:A<$B和τ:B<$C的合成是策略τ σ:A<$C,σ和τ对A中的参与者移动或C中的对手移动做出反应,可能是在B中的一系列内部交换之后。恒等式和复合的形式定义也是可能的,但需要引入一些符号。当一个战术正在改变并且由对手的移动开始时,它被称为合法的。合法策略集记为LA。偶数长度的合法策略集,或等价地以玩家移动结 束 的 合 法 策 略 集 ,记为Leven。康 威 博 弈 A 的恒等式是战略如下:IDA ={s∈Leven| ∀t ∈ LA⊥⊗A,t是s|A⊥ =t|A}。P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171175一个小C⊥联系我们两个策略σ:AB和τ:BC的合成是τσ:下面的ACτσ={s∈Leven| ∃t ∈ P ABC,t|甲乙丙∈σ,t|和218c∈τ,t|素八=s}。康威对策之间的张量积在范畴Y上产生了一个双函子,它使得范畴Y是-自治的,也就是说,是对称的么半群闭的,有一个对偶对象记为。范畴Y不仅仅是非自治的:它是紧闭的,在这个意义上,存在一个i somorfi s m(A<$B)<$$>=A<$$>B <$naturalinAandB. Asinanycomp act闭范畴,对偶对象同构于么半群结构,也就是康威博弈1因此,对于每个康威对策A,么半群闭包A同构于A。2关键观察:Y类没有二元产品90年代初,在线性逻辑和程序设计语言语义学的背景下,Y范畴被重新发现。作为一个非自治范畴,范畴Y定义了乘法线性逻辑(MLL)的一个模型。在这个模型中,MLL的每个封闭公式F都被解释为一个Conway对策[F];公式F的每个证明π都被解释为Conway对策[F]的一个获胜策略[π]。这种解释提供了一个精确而生动的证明图片,被理解为在削减消除过程中相互作用的符号装置。由于MLL只是线性逻辑的一小部分,许多作者试图适应Y范畴,以捕捉更大或更有趣的逻辑片段。一个特别抗片段是乘法加法线性逻辑(MALL),它是MLL扩展与加法连接和常数0和。 每一个具有有限产品的自治类别都定义了一个MALL模型。可惜的是,Y类没有二元产品。据我们所知,这一众所周知的事实的证据在文献中找不到。我们在下面介绍一下,Y−是一个负康威博弈。康韦的消极游戏。一个康威对策A称为负对策,当A的每一个非空局都由对手的一步棋开始。范畴Y−被定义为Y的全子范畴,其对象是负康威博弈。范畴Y−是对称monoidal闭的。对称的么半群结构继承自范畴Y,而Y−的么半群闭包则略有不同。这里引入范畴Y−是因为它有有限个176P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171∗⎨→−−→−→产品.这个范畴的终端对象是康威博弈1。两个负康威博弈A和B的卡耐基乘积是记为AB的负康威博弈,定义如下:• 它的位置集是A的位置集和B的位置集的不交和,其中A和B的两个根A和B被标识为A B的根A&B&。这种构造类似于区域理论中的提升和,• 其对手从根位置&开始的移动有两种:阿罗阿B如果在康威博弈A中,如果在康威博弈B中,• 其从分量A中的位置x的移动恰好是从康威博弈A中的x,极性相同x→y在博弈A&B中在博弈A中x→y。• 其从分量B中的位置x的移动恰好是从康威博弈B中的x,极性相同不难看出,配备有精确投影策略AB-→A和AB-→B的博弈AB在范畴Y中定义了A和B的一个卡累利阿积。本节的结尾专门证明:命题2.1范畴Y没有二元乘积。证据 健忘函子U:Y−Y有一个右伴随Neg:YY−,它将每个康威博弈A=(V,E,λ)与否定康威博弈Neg(A)=(VJ,EJ,λ)相关联,通过从根节点开始删除每个玩家移动获得:EJ= E\ {(x,x)∈E|λ(λ →x)=+1},然后移除从图(V,EJ)中的根不可访问的V中的每个位置:VJ={x∈V|在(V,E,J)中存在一条从根到x的路径。作为右伴随,函子Neg保持极限。我们从矛盾出发,假设每对Conway对策A和B在范畴Y中有一个记为A×B的卡积。然后,图像Neg(A×B)为P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171177⟨ ⟩ −→×+这个积同构于范畴Y−中的卡积Neg(A)Neg(B)。现在,当康威博弈A的对偶博弈A为负时,它被称为正博弈我们认为两个正的Conway对策A和B在Y是一个正的Conway对策A×B。注意,康威博弈A是正的i ≠ Neg(A)= 1。与两个正博弈A和B的乘积相关联的负博弈Neg(A×B)等于Neg(A)Neg(B)= 1 1 = 1。 因此,A×B的博弈设Y+表示Y的由正Conway对策构成的全子范畴。由于Y+是Y的一个全子范畴,我们已经建立了如果Y有二进制积,那么Y+也有二进制积我们通过证明Y+没有二进制乘积来结束命题2.1的证明考虑负博弈B解释布尔值,有四个位置,q,真,假,一个对手移动设X=B表示通过对偶化得到的正对策B.考虑两个正对策A和B,并假设A×B是它们在Y +中的Cartesianproduct。Letemorphismσtrue:X−→A在categoryY+中表示包含对策的BAB类似地,设τbool:X−→B表示包含对策的B<$B的最小策略B当炸弹爆炸的时候,它就意味着一个错误或错误。Letσtrue,τfalse:XAB表示Y+中的唯一态射,使得(1)σtrue=π1<$$>σtrue,τfalse<$$> τfalse=π2<$$>σtrue,τfalse<$对于π1:A × B −→ A和π2:A × B −→ B,是与康威博弈A和B在Y中的投影。 对(1)的仔细检查表明,策略τσtrue,τf al ee满足以下形式的一种形式:<$B<$$> A×B→ q <$$> A×B→ q <$x。对于A×B的位置x和参与者移动→x;并且策略π1:(A×B)A包含以下形式A×B对于A×B的位置y1和对手移动→y1。类似地,策略π2:(A×B)B包含以下形式的博弈:A×B178P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171→×−→−→+对于A×B的位置y2和对手移动n →y2。注意,在A×B中,两个位置y1和y2可以相等。现在,设ν:X−→A×B表示包含该策略的最小策略:B令νJ:X−→A×B表示包含所有形式的对策的最小策略B对于y,一个位置,使得xy是A B的对手移动。两个等式π1ν = σ真= π1νJπ2ν = τ真= π2νJ。立即从这些定义中得出。因此,存在不止一个态射X−→A×B,使得卡图对σ真:XA和τ真:X可交换B. 我们的结论是,没有二元产品。这就是命题2.1的证明。Q注:有另一种更直接的方法来证明范畴Y没有有限产品,这就是证明范畴Y没有终结对象。然而,这种替代论证并不那么具有决定性,因为在形式上有可能在范畴Y上增加一个初始对象和一个终结对象,而不打破自我二元性。3Blass问题我们刚刚在第二节中看到,·类别Y是非自治的,但没有有限的产品,·它的子范畴Y−是对称monoidal闭的,并且有所有的乘积。这就解释了为什么游戏语义学通常更关心范畴Y-的变体而不是范畴Y的变体。从表面上看,为了解释建立在λ演算之上的编程语言,自对偶性不如笛卡尔性重要再说了,指数模态!线性逻辑在范畴Y-(或一个变体)中比在范畴Y中更重要。通过从范畴Y-开始,人们得到直觉线性逻辑(ILL)的模型,其范畴公理化确保:P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171179∗⊗ ⇑⊥⊥⇓⇑与comonad相关的kleisli类别!是carnival封闭的,因此定义了一个带有乘积的简单类型λ演算的模型,参见[14,5,10]以及其他作品。通过在类别Y-的变体中进行选择,以及在comonad的变体中进行选择,可以生成各种各样的模型。λ演算,其中一些捕捉了特定语法编程语言的本质(参见完整的抽象结果)。这种方法很好,也很有成效。 但我们认为,缺乏 Y−范畴的自对偶性是博弈语义学的一个严重的概念局限。我们的目标是通过重新理解Y−作为包含产品和副产品的更大的自主类别Z的一部分,来澄清这个主题的基础。在本节中,我们试图推断出从所谓的Blass问题的分类重新表述的Z类我们继续尽可能保持范畴Y−和它的相反范畴Y+之间的对称性,以便让意想不到的结构出现从对称性。这为第5节做好了准备,在第5节中,我们构造了一个Z类的候选者,Z是一个异步博弈和无辜策略的类别。提升函子之间的第一个附加。我们从所谓的提升函子<$:Y−−→Y+开始分析,它与每个负康威博弈A相关联,正康威博弈<$A定义如下:·位置A是A的位置或新位置A,· 唯一从A开始的移动是参与者移动A →A到A的根A,·从A中的位置开始的移动与A中的相同,具有相同的极性。通过对偶,存在一个提升函子:Y+−→Y−,由以下等式A =(有趣的是,函子是函子的左伴随- 是的 这个附加项在康威博弈中的意义非常简单。 考虑一个负康威博弈A和正康威博弈BY+(A,B)和Y−(A,B)的元素分别是A的获胜策略和A的获胜策略B,分别。 注意,A和B都是正康威博弈因此,在康威博弈A(A)B和AB中,由对手移动开始的策略是相同的:在每种情况下,AB中的假移动之后是一个策略。这导致了策略Y+(A,B)和Y−(A,B)之间的双射,其中在A中是自然的,B.由此得出,它是左伴随的。这个附加物诱导了一个关于Y−的单子和一个关于Y+的单子,或者是一个通过两次两次地产生的单子。注意Y−上单子的变体已经被观察到了,典型地在竞技场游戏的文献180P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171−→−→↑↓提升函子之间的第二个附加。从现在开始,我们将重点放在另一个附加项↑E ↓上,它是从附加项E派生出来的,它在将博弈表述为连续传递风格模型中起着基础性作用注意,范畴Y+有余积,因为它的对立面类别Y-有产品。由此可以得出函子的因式分解为:(一)−→Y(二)−→Y其中,Y−是Y−关于余积的自由完备化。在[2]中,这种完备化也被称为族构造我们回顾:• 一个对象是一个族{A i|i∈I}的负Conway对策A i,由集合I的元素索引,• 态射{A i|i ∈ I} −→ {B j|j ∈ J}包含一个重索引函数f:I−→J和获胜策略σi:Ai−→Bf(i),对每个指标i∈I.对偶地,提升函子将因子分解为:(三)−→Y(四)−→Y其中,Y+是Y−相对于乘积的自由完备化注意,范畴Y+与范畴Y−相反。通过将得到的函子组合在一起,得到两个新的↑:Y−(2)(三)−→Y+,↓:(一)−→是的。我们对提升函子的符号和已经表明,我们认为BYY−是一个正对策的范畴,BYY+是一个负对策的范畴。通常,我们喜欢把一个对象看作是一个族,{A i|i∈I}的负博弈,作为一个正博弈,其初始移动参与者是指数i∈I。我们将在本节后面再讨论这一点有趣的是,函子↑与函子↓左伴随。 假设一个家庭A ={A i|i ∈ I}的负Conway对策,以及一族B ={B j|j∈J}的正Conway对策。族A被↑转移(或提升)到正康威对策i 最后,族B被↓转移(或提升)到由负Y−−Y++Y+Y−+−P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171181∈−·康威游戏&。现在,我们有一系列集合之间的双射:<$Y−(A,↓B)<$=<$i∈IY−(Ai,j∈J<$Bj)通过定义<$Y−,=n=n(i,j)∈I×JY+(nAi,Bj)thankstothen En,=通过定义Y+,可以很容易地确定Y+在A和B中的自然性。Y-作为线性连续范畴。作为具有乘积的对称monoidal闭范畴的自由完备化,范畴Y−是对称monoidal闭的。functor:(2)(−−):Y−×Y−− →Y−定义在正Conway对策族上,如下所示:(3){Ai|i∈I}<${Bj|j∈J}={Ai<$Bj|(i,j)∈I×J}.Monoidal闭包A−·B定义如下:(4){Ai|i∈I}−·{Bj|j∈J}={&i∈I(A<$i<$Bf(i))|f∈I→J}因此,康威博弈A-·B的初始玩家移动(等价地,族A-·B的指数)是从A中的初始玩家移动集合I到B中的初始玩家移动集合J的集合论函数f。 这种定义A B初始移动的方式不符合博弈语义学的一般哲学,即避免像集合论函数空间这样的“外延”构造。非常幸运的是,我们可以将这种构造专门化到B=n是以空的康威博弈1为唯一元素的单例族的情况。 这就定义了所谓的线性连续范畴,也就是说,一个对称的monoidal范畴,它的有限余积在张量积上是分布的,并且它的对象是一个可指数化的对象。此外,我们认为,C类代数Y −的内函子A<$→(A−·)与内函子A<$→(A↓)相交.Y−和我们已经指出,我们喜欢把范畴BYY-看作是一个正康威博弈范畴这是由前面提到的函子<$Y −−→ Y+的存在所证明的,它传递每个族{A i|i∈I}的负对策积极的游戏与初始移动的指数i我,其次是发挥我。函子是忠实的,对象是单射的。因此,范畴Y−是182P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171和.−++−·↑ E ↓······↓··它与它在几何学Y+中的像同构,其中记为Y+−。类别Y+−•Y+−是•可以直接定义如下。 ·的对象Conway游戏,其中:• 每一步棋都是由参与人走的• 每一步棋都是由对手走的Y+−的态射A−→B是获胜策略σ:AB,玩家的每一步棋·A→A中的x,存在一个参与人移动,B,使得对策AB→xB→xy是策略σ的元素。对偶地,函子<$Y+−→Y−定义范畴当Y−+被定义为Y+ −的最小值y时,Y + − = Y−+。Itisnot···很难看到得到的函子:↑:Y+−−→Y−+,↓:Y−+−→Y+−。与限制于子范畴Y+−的提升函子和一致Y和Y的 这是我们对↑的现在,设Y−+表示Y−的全部子空间,其中Y−+是第一个对象,设Y+−表示Y+的全子范畴,其对象为Y+−·相反地,类别Y+−与类别Y−+相反。• . 通过这里有一个重要的观察:范畴Y−+是共-kle是位于电荷Y−+上方的电荷,由电荷↑↓引起。Itisnot·确实很难检查集合Y−+(A,B)offmorphismsbettwentwo关于Y−+的一个y博弈A和B的n个等式C,等于f的集合Y+−(↓A,↓B)范畴Y−+中的态射•Y−+是• . 这意味着,连续性的计算与计算Y+−相同。类别Y−+·因此定义了彼得·塞林格所谓的(线性)控制在[15]中。范畴Y−+是与之相关联的中心映射的范畴。此控制类别Y−+·.这是理解家庭由Samson Abramsky和Guy McCusker在[2]中构建,极化Olivier Laurent在[9]中对博弈的描述,以及Peter Selinger在[15]中对控制范畴的表示附加功能模拟同步。经过长时间的讨论,我们准备阐明附加项的计算意义↑E↓。SupposethaA表示在Y+−中的一个连续博弈,而Ba·n egati veCo nwaygameinY−+. EveryelementofY+−(A,↓A<$$> ↓B的 egyσ,它等待A<$$>中的对手移动m:<$A→x,在收到m后,在↓B中走虚步,等待对手走步n:在B中n → B→y,并在接收到n后继续。对称地,Y−+(↑A,B)的每个元素都是一个↓ AB的策略τ,其中对于nOp p,B)是一个战略-P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171183·⊗−→······移动n:B中的B→y,在收到n后在↓A中下虚移动,在A中等待对手移动m:A→x,并在收到m后继续。 在这两种情况下,策略σ或τ等待两个输入m:这样,两个策略σ和τ实现了m在A中和n在B中的同步输入:策略σ通过在A中询问然后在B中询问(按值调用顺序)来模拟A和B的同步,而策略σ在B中询问然后在A中询问(按名称调用顺序)。康威游戏AB 关于同步的讨论有一个明确的对应。与附加项↑E ↓相关联的函子:(5)(Y+−)op×Y−+−→Set.··在Conway博弈中分解为函子:op(6)(−−):(Y+−)×Y−+−→Y−+后合成到全局元素函子Y−+Set,它将每个负康威博弈与其获胜策略集相关联。康威博弈AB的定义就像A→B一样,只是最初的对手移动是一个参与者在A中移动和一个对手在B中移动的对(m,n)。布拉斯的问题康威博弈AB的定义与安德烈·布拉斯在他的线性逻辑博弈论中给出的定义一致。有趣的是,初始动作的同步是在这正是导致所谓的布拉斯问题的原因。 问题是:似乎有一种自然的方式来建立一个消极和积极的游戏类别-不幸的是,这种自然的结构确实有效,因为它定义了一个非联想结构,参见Samson Abramsky在[1]中的综合说明。布拉斯问题可以用下面的方式明确地重新表述作为任何原函子,函子(5)诱导一个具有Conway对策的范畴Y·Y+−和Y−+作为对象,并且:··• 两个正康威博弈A和B之间Y+−的态射,• 两个负康威博弈A和B之间的Y−+态射,• 从积极博弈A到消极博弈B的策略• 从消极博弈A到积极博弈B没有态射范畴Y ·的合成律是从范畴Y+−和Y−+的合成律导出的,同样也是从函子导出的。屁股或ciativity··由(5)的双函数性确保。当我们试图替换两个范畴Y+−时,就会出现布拉斯问题和Y−+在Y·的构造中,通过它们的Kleisli范畴Y+−和Y·-+。184P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171−→−→⊗·∗假设确实有人试图在kleisslicategoryY+−中构造态射hA:AJA,as策略σ:AB,和d amorphismσ:B在co-kle中的B j是licat egoryY−+。这意味着将函子r(6)推广为函子op(7)(−−):(Y+−)×Y−+−→Y−+。布拉斯问题相当于这样一个事实,即没有这样的函子(7),但只有一个函子:op(8)(−−):(Y+−)<$Y−+−→Y−+。当re(Y+−)opY−+是(Y+−)op×Y−+的一个变量,而复合和张量积之间没有内在的变化规律时,定义见[13]。换句话说,平等:(idAJh B)(h AidB)=(h AidBJ)(idAB)不一定是 真的。现在,观察函子(6)和(2)通过自然同构AB=(A B<$)<$.因此,将函子从范畴Y+−和Y−+扩展到它们的类范畴Y+−和Y−+,··+− +−将函子从Y·推广到它的kleisli范畴Y。 这使得能够应用这个著名的事实理论的单子,见[6,13],即函子在Y + −上定义了一个预幺半群结构,因为在C上的线性连续幺半 群 是 强的,但不是连续的。向Z类靠拢。我们把Blass问题归结为线性变换模A<$→((A-·)-·)强但不交换的性质. 这为我们提供了一个方法,逻辑:找到范畴Y+−的类似物,其中线性连续·单子A<$→((A−·)−·)将是可交换的。 更重要的是:为了为了得到一个-自治范畴,我们希望这个线性连续单子等价于(作为单子)恒等式。第5节中介绍的异步游戏类别正是为此目的而设计的4异步游戏语义在本节中,我们回顾了[12]中给出异步博弈的最初定义有三种方式。首先,我们考虑一个良好的事件结构的异步游戏,为了将它们与康威游戏。这只是一个细节的介绍,因为我们所有的定义在非良基异步博弈中都能很好地我们还添加了一个不兼容关系#P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171185∈联系我们在游戏的移动之间,为了解释线性逻辑的加法连接词和常数最后,我们用在{−∞,−1,+1,∞}中的一个支付点来区分参与者位置(+1,+∞)和对手位置(−1,−∞),以及内部位置(+∞,−∞)和外部位置(+1,−1)。事件结构。事件结构(M,≤,#)是事件的偏序集合(M,≤),其配备有二元对称不相关关系#,验证:• 集合m↓ ={n∈M|n≤m}对于每个事件m∈ M都是有限的,• 对于任意事件m,n,p∈M,m#n≤p蕴涵m#p.两个事件m,nM在m#n时称为不相容,在其他情况下称为相容.两个移动m和n在相容时称为独立移动,在相异时称为相异移动。我们在这种情况下写mIn岗位 事件结构A的位置是(MA,≤A)的有限向下闭子集,由成对相容事件组成. A的位置集合记为DA。位置图。每个事件结构A诱导一个图GA,其节点是位置x,y∈DA,其边m:x-→y是验证y=x+m的事件,其中+表示不交并,即y=x m并且移动m不是x的元素。 一个事件结构被称为有根据的当图GA是良基时。异步游戏一 个异步博弈A =(MA,≤A,#A,λ A,κ A)是一个良基事件结构(MA,≤A,#A),它的事件被称为博弈的移动,在移动上有一个极性函数λ A:MA−→ {−1,+1},在位置上有一个支付函数κ A:DA−→{−∞,−1,+1,+ ∞}。极性+1的移动(分别为-1)被称为玩家(resp.对手)移动。一个玩家(resp.对手)位置是支付在{+1,+∞}(分别)的位置。在{−1,−∞}中)。一个外部的(resp. internal)position是一个payo在{+1,-1}的位置(resp. in{+∞,−∞})。康威的基本博弈异步博弈A的位置图定义了一个康威博弈GA,其中移动x→y的极性由底层移动m的极性给出,使得y=x+{m}在异步博弈A中。为了简单起见,我们将GA的策略集写成PA而不是PGA。 GA中的结构比A中的结构通常的康威游戏,因为每个位置都有一个支付点,移动可能是186P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171∈∈在游戏中,如下所述。G A的外部位置集记为dD<$A。你好。当路径s和sj的长度为2时,我们记s∈1SJ,其中s=m·n,SJ=n·m,对于两个移动m,n∈MA。路之间的同伦等价关系定义为包含等价关系1的最小等价关系,并且在复合下是封闭的我们也在图中使用符号m来表示两个(必然独立的)移动m和n是置换的。同伦这个词在数学上是由Philippe Gaucher和Eric Goubault [4]关于有向同伦的工作定义的。事实上,每一个异步博弈都定义了一个有向单纯集,其中路径之间的有向同伦与我们的置换等价一致。战略一个异步对策的策略σ是下竞争对策GA的一个策略,更重要的是,策略σ中的每一个博弈方s:n−−→x都有其正收益为n:+1或+∞的目标位置x. 当A的策略σ在潜在的康威博弈GA中获胜时,它就获胜了。当σ是异步博弈A的获胜策略时,我们写σ:A。无辜。我们在[12]中重新表述了竞技场游戏中常见的无罪概念,如下所示。一个策略σ被称为无辜的,当它在下面的意义上是侧一致的和前向一致的向后的一致性。一个策略σ是后向一致的(见图1),当对于每个策略s1∈PA,对于每个路径s2,对于每个移动m1,n1,m2,n2∈MA,它遵循s1·m1·n1·m2·n2·s2∈σ和<$(n1<$Am2)和<$(m1<$Am2)的<$(n1<$An2)和<$(m1<$An2)且s1·m2·n2·m1·n1·s2∈σ.向前一致性。一个策略σ是前向一致的(见图2),当对于每一局s1PA和每一步m1,n1,m2,n2MA,它遵循s1·m1·n1∈σ和s1·m2·n2∈σ和m1Im2和m2ln1的m1I n2和n1I n2,且s1·m1·n1·m2·n2∈ σ.P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171187、、你,,,1,,,∈、、、2、、、S2、、、S2n2,乌斯季2,n,n1M2 ,,M2 ,,、、、,m1σ3,、、、你,,,,...、、、你,、、、,∈σn1,.....、、、,n1,...,n2你好,m1,m2、、、S1m1,m2、、、S1Fig. 1.后向一致性n2 ,n,n1,M2 你,、、、,m1M2、、、、、、、、、、σ3∼σσ3 ,,,,,,,,,,,,∈σn,1,nn,,n,,,,2002年.....、、、m1,m2M1 ,m2、、、、、、S1S1图二.前向一致性位置战略。一个策略σ:A称为位置策略,当对策略σ中的任意twplays1,s2:A−−→x,以及GA的任意twpatht:x−−→y,有:s1<$s2和s1·t∈σ <$s2·t∈ σ。命题4.1([12])每个无辜策略σ都是位置策略。注意,每个位置策略都由DAitreaches的位置集合来表征,定义为dasσ·={x∈DA,s∈σ,s:<$A−−→→x}。188P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)1715全命题线性逻辑的一个无辜模型异步游戏的提升。任何异步博弈A的提升策略A是通过提升移动集合MA定义的异步博弈,P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171189⊗{−}对手移动m,并将内部和玩家支付给异步博弈的根博弈A的根博弈A。操作A是双重定义的。异步博弈的张量积。两个异步对策的张量积A BA=(MA,≤A,#A,λA,κA)和B=(MB,≤B,#B,λB,κB)由极化事件结构(MA+ MB,≤A+ ≤A,#A+#B,λ A+ λ B).因此,A和B的基本康威博弈等于A和B的基本康威博弈的张量积。下表给出了头寸xy的支付κAB(xy),其中支付κA(x)和κB(y)出现在第一行和第一列。⊗−∞−1+1个+∞−∞−∞−∞−∞−∞−1−∞−∞−1+∞+1个−∞−1+1个+∞+∞−∞+∞+∞+∞注意,这个表在A和B中是对称的,并且一个内部位置与另一个位置的张量积总是内部的。线性游戏 线性博弈被定义为一对{π |A我|i ∈ I}由一个极性π +1,1和一族(Ai)i∈I组成的以I为指标的异步对策. A的位置被定义为任何异步游戏Ai. A的位置的分量是它在其中出现的异步博弈Ai。当A的位置是它的分量Ai的根时,它被称为初始位置。当π=+1时,A中的每一个初始位置都需要有一个正的支付点,当π = −1时,A中的每一个初始位置都需要有一个负的支付点。当π = −1时,线性博弈被称为负博弈;当π =+1时,线性博弈被称为正博弈。抬起来。负博弈A={-1|A我|i∈I}是正博弈↓A={+1|&i∈ I<$A i}由一个具有极化事件结构的唯一异步博弈&i∈I<$A i组成,极化事件结构是<$A i的极化事件结构的不交和,其中<$Ai和<$Aj中的所有移动不相容,当i j。注意,i∈I<$Ai的基本康威博弈是在范畴Y−中,每个Ai的潜在康威博弈的乘积。190P. - A. Melliès/Electronic Notes in Theoretical Computer Science 122(2005)171defdefdef.. .{−||∈}|∈ }.- 是的...JJ−∞.乘法。两个正对策A =的张量积A<$B{+1 |A我|i∈I}且B ={+1 |B J|j∈J}通过同步A和B的初始位置来定义:def(9)AB ={+1 |A iB j|(i,j)∈ I × J}正线性博弈和负线性博弈的张量积从(9)推导为:ABABA B..当A为正而B为负时,=(↓A)<$B当A为负而B为正时,=(↓A)<$(↓B) 当A和B为负数时。的. . 两个线性博弈A和B的乘积是由德摩根推导出来的。..def. .你... .⊥⊥.平等: A. B =(A.
下载后可阅读完整内容,剩余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直接复制
信息提交成功