时间表的几何形状和关联性研究 - 2007年Harmer et al.设计的证明模型

可在www.sciencedirect.com在线获取理论计算机科学电子笔记286（2012）273-289www.elsevier.com/locate/entcs时间表的图形基础Guy McCusker1，John Power2和Cai Wingfield3，4巴斯大学计算机科学系英国巴斯BA2 7AY摘要在2007年，H a r m e r，H y l a n d M e ll i i `e s gave ave a v e f o r m a m a m a t i c a f o r g a m e s m at i c n u r g a m e s m a t i c a n i c a n g a m a m a t i c n u r g a m e s m a t i c a n t i c a n g a n t i c a n t i ca n g a n t i c a n t i c a n t i c a n t i c a n g a n t i c n g a n t i c a n t i c a n t i c a n t i c n g a n t i c n t i c an t i c n g a n t i c n t i c a n t i c n t i c n g a n t i c n t i c a n t i c n t i c a n t i c n t i c a n t i c n t i c n t i c他们的定义本质上是组合的，但研究人员在实际描述时间表时经常会画出图片。此外，证明附表的组成是关联的，涉及繁琐的组合细节，而在图片方面的证明是直截了当的，反映了平面的几 何 形 状 。 在 这 里 ， 我 们 给 出 了 一 个 几 何 形 式 的 时 间 表 ， 证 明 了 它是平等的， 以Harmeretal。的设计，并将通过对组合物的一部分进行预处理来利用价值。保留字：游戏语义学，几何学，时间表，合成，关联性。1介绍近几十年来，游戏语义已经成为编程语言语义的标准形式之一[2，3，4，12，16]。2007年，Harmer、Hyland和Melli为一个大型基金会提供了一个大型基金会[9]。这种结构是一种组合装置，即调度函数（或调度它描述了一种游戏的交错;游戏A和B中的位置由下式给出：A中的位置、B中的位置以及对这些位置的合并进行编码的调度。然后，他们定义了一个组合的时间表。形式上，调度被定义为函数e：{1，. . . ，n} → {0，1}，条件是e（1）= 1和e（2k + 1）=e（2k）。 因此，schedulee本质上是一个长度为n的二进制字符串，其中e的定义域从左到右索引字符串，并且1和0在第一个1之后成对出现（参见第2节）。 例如，1001111001和1001100001是调度{1，. . . ，10} → {0，1}。1Email：g. a. mcc u s k er@ b at h. AC. u k2Email：a. J. 我们是一个很好的朋友。AC. uk3Email：c. a. J. 我想我是个很好的朋友。AC. uk4由EPSRC的博士赠款支助。1571-0661 © 2012 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2012.08.018274G. McCusker等人/理论计算机科学电子笔记286（2012）273··················(a) 进度图示例。·(b) 另一个进度图示例。·····················(c) 要进行合成，请对两个时间表进行变形，以便识别内部节点的两个图像，从而形成合成图。(d) 复合时间表是通过沿着边跟踪来实现的，从右边的第一个节点开始，每当到达内部节点时交换边Fig. 1.示例时间表和组成。研究人员通常使用图形表示在页面或黑板上描述时间表[5，7，11，12]。例如，图1（a）和1（b）是上述两个时间表的图形表示。复合材料也通常以图形方式描述，其方式与[9]中将进度表描述为订单关系对所暗示的方式相同。图1（c）和1（d）描述了上述两个时间表示例的综合。虽然许多人精确地画出了这样的图表，但还有一种常见的做法是省略线条-即戏剧在A中，将在标题“A中B“下面绘制，并在A中下面的这种以图画形式编排的戏剧仍然是真正的时间表图表，本文对时间表的图形定义涵盖了它们;涉及其组成的论点与本文的论点基本从某种意义上说，可以画线的事实意味着这些图片代表了时间表。这种情况引起了我们在本文中探讨的几个自然问题。首先，在第3节中，我们将那些从时间表中产生的图片进行排序。··G. McCusker等人/理论计算机科学电子笔记286（2012）273275在第4节中，我们正式证明了Harmer et al.'的组合定义和我们的几何定义是一致的。我们还定义了一个复合的时间表在几何方面，并表明它同意Harmer等人。S.在第五节中，我们证明了复合的结合性，给出了左恒等式和右恒等式，从而展示了范畴日程表Harmer等人也断言，时间表的组合产生一个类别，但他们在[9]中没有包括证明Harmer et al.'中的一个证明的条款是combinatorially繁琐，而在几何方面，它直接遵循的结合并置在平面。我们对时间表的图形定义是在Joyal和Street的monoidal范畴弦图的框架中设定的人们可能倾向于使用图的代数定义;然而，为了正确地考虑研究人员绘制的图，人们需要精确地考虑代数图在平面中的嵌入意味着什么，这需要与第3节和第4节以及[14]中类似的讨论。也可以使用[19]，cf. Mellies[18 ]第10段。我们计划将这种图形方法扩展到包含指针图[5，8，12]，并以这种方式重新制定Harmer等人的所有的文件中的几何术语。2时间表的组合基础在这一节中，我们回顾了[9]中的时间表和时间表组合的组合定义定义2.1（如Harmer et al.[9]）一个函数是一个函数e：{1，. . . ，n} → {0，1}满足e（1）= 1和e（2k +1）= e（2k）.计划e：{1，. . .，n}→ {0，1}是0 s和1 s的序列。我们写|e|为了那根长长的骨头。我们所有人都在等着|e| 为 了我们的未来，|e|1对于在该等式中的1个数字，|e|=n=|e|0+|e|1 .一、在[9]中，调度函数也被称为调度，但我们将注意不要将其与后面的定义3.4混淆。当需要消除歧义时，我们将后者称为“图形时间表”。在定理5.6中，我们这将证明这些定义是等价的。示例2.2以下是调度函数：(i) 1001111001和1001100001是我们已经在图1（a）和1（b）中看到的示例。(ii) 任何非空前缀（或限制[9]）的时间表是一个时间表。定义2.3（如Harmer et al.[9]）我们将使用符号e：p→q，当e这是一个持续时间：{1，. . . ，p+q}→{0，1}，其中|e|0=pand|e|1=q。设e：p→q是这样一个时间表。写[n]来表示集合{1，. . .，n}，我们将对[n]+f[n]和d[n]的每个元素的集合-f [ n]的所有d元素的集合进行排序。时间表e对应于一对保序的集体满射嵌入eL：[p]n→[p+q]和eR：[q]n→[p+q]，其中eL是276G. McCusker等人/理论计算机科学电子笔记286（2012）273e−1（0）<$[p + q]的保序满射，且eR同样是e−1（1）的满射。这一新的计算方法可以将L（x） π2（i（pk））· 只有节点接触边：i（u）（{u，v}×R）=i（U+V）。注意，这个条件意味着z0严格包含在（u，v）×R内。我们可以写Sm，n：U→V，当一个调度Sm，n有内部节点U和V的集合时。由于边缘上的方向总是可以恢复的，因此我们可以在手工绘制明细表时安全地省略箭头例如，图1（a）示出了调度4 -6，图1（b）示出了调度6- 4，并且图1（d）示出了调度4- 4。接下来我们需要两个时间表是“相同的”的概念。Joyal和Street定义3.5设Sm，n=（U，V，m，i）和S′=（U′，V′，m′，i′）是具有embedding s i：Rangi→[u，v]×Randi′：Rangi→[u′，v′]×Rre s pectively.如果存在连续函数h：n=[0，1]→R2suchthat，则称n可变形为n′• 对于acht∈[0，1]，h（−，t）是一个定义在gL ut →[ut，vt]×Rofa在平面上的空间，使得h（U，t）<$Lut，h（V，t）<$Lvt.• h（U，0）=i（U，0）是一种定义了h（U，0）=i（U，0）的连续函数的方法h（V，0）∈Lv且u0=u且v0=v。• h（k，1）=i′（k′）是k（k′的所有值）的一种形式，它是在h（k，1）= i′（k ′）时的一种形式h（U，1）<$Lu′和h（V，1）<$Lv′，u1= u′和v1= v′.那么我们也可以说，时间表Sm，n是时间表的变形′m，n. 我们称h为形变，记为“Sm，n <$S ′“。由于变形意味着每个调度中的节点和边的集合是双射的，所以我们可以自动地将它们关联以给出变形类的节点和边的例如，再看图1（d）中的时间表，我们可以通过在平面上平滑地操纵它来变形，确保节点的垂直顺序不被打乱，并且在每个时间点它都保持一个时间表。图SG. McCusker等人/理论计算机科学电子笔记286（2012）273279························(a)t=0。（b）t=1/2。（c）t = 1。菲格3.第三章。“时间表”显示了图1（b）中所示时间段的数据。为了清楚起见，已经省略了用于指示方向的其他部分。3 展示了一个例子。在重新使用之前，可以在组合明细表的“清理”过程中专门使用这样的变形由于具有其平面嵌入i的平面图Γ可以平凡地变形为具有单位嵌入的平面内图i（Γ），因此我们经常识别具有所选（或任意）嵌入的图，其中不需要区分。类似地，我们通常将变形类代表取为选择为具有单位嵌入的平面的子集的图例3.6对于任何时间表，下面是变形的例子，我们将在本文中多次使用• 在飞机上翻译那个时刻表。• 平面中的水平或垂直缩放• “分段”垂直缩放，通过将平面除以有限数量的水平线，然后对每条线应用不同的缩放因子来这将允许我们在任何需要的地方放置时间表的节点，而不会改变它们的顺序或4附表的构成为了研究类似于时间表的一类时间表，我们需要具体描述时间表的组成。两个进度表的组合将通过在平面中从两个组件构造一个更大的渐进图，然后从中提取路径来执行。本质上，每个进度表嵌入其中的条带将在平面中定位为在一条垂直线处相交我们将开始跟踪右侧组件明细表中的路径，但切换到280G. McCusker等人/理论计算机科学电子笔记286（2012）273y1y2×a1y3、×a2y4}×a3菲格 四、 一个没有使用任何一个零件的地方将被视为一个非常好的地方。图中的水平线和右边的条带是将具有因子a i的比例应用于每个片段的结果，其中虚线直线表示片段的线性比例。另一个时间表，每当我们遇到它，并继续交换来回时-永远可能的。事实上，这将为我们提供通过两个时间表的所有节点的唯一的直到变形的路径，并且这样的路径本身将是一个时间表。定义4.1设Sm，n=（U，V，m，i）和S′=（V，W，m′，i′）是两个时间表（我们称之为S和S′）n，r为了简洁起见）。 我们首先观察到， 的平移和分段垂直标度允许我们假设i（V）=i′（V）。我们把这样形成的渐进平面图称为（2重）合成图;它有结点U + V + W，在S和S ′中的每条边都有一条边。（我们现在将不区分顶点集U，V，W和它们所选择的嵌入i（U），i（V）= i′（V），i′（W），其中上下文清楚地表明了“∈”的含义。让我们把不在组成图的外部边缘上的任何节点称为内部节点，而把所有其他节点称为外部节点。为了形成S和S′的合成，写作SS′，我们将从合成图中提取一条路径。最终，我们的合成将只有节点U+W。现在我们也考虑V中的节点，以便所有边都有端点。由于S和S'是时间表，并且所有边都是渐进的，所以U + V + W在组成图中可以是自上而下有序的，其中顺序相邻的节点由至少一个边连接。 从S ′中的第一条边开始，我们追踪一条由S和S ′中的边组成的路径。在到达每个外部节点时，我们从它获取唯一的向外边在到达每个内部节点时，我们从它获取位于另一个时间表中的向外边，该时间表位于我们获取的向内边中当我们到达一个没有向外边的节点时，我们停止为了完成合成，我们丢弃所有没有选择的边，并解密所有内部节点，将相邻的边粘合在一起（如图2所示）。请注意，被移除的边是那些包含扩展的这给出了SS′作为一个时间表的数据（U，W，P，κ），其中P是以这种方式由边形成的路径，κ是该路径在平面中的包含映射引理4.2在定义4.1中选择的路径是通过组成图的所有节点的唯一路径（直到变形）。G. McCusker等人/理论计算机科学电子笔记286（2012）273281U4V6········V6W4····由·组成·····(a) 由于它们共享V6，因此可以组合这些调度.这些是来自图1（a）和1（b）的时间表。U4V6W4·U4W4·····················(b) 我们分段垂直规模和翻译两个时间表，使两个图像的V6的识别，形成一个组成图。(c) 我们按照定义4.1中指定的方式沿着路径跟踪，最后解密V6的点。图五.附表的组成证据令表S和S′如定义4.1所示。考虑一下组成图。 由于每个组件进度表本身就是一条路径，因此我们可以选择向外边的节点只有内部节点--那些共享的节点在S和S之间。在组成图中具有多于一个向外边缘的内部节点x(I) 如图6（a）所示。从x向外的两条边都直接通向另一个内部节点。在这种情况下，选择任意一条边都会产生相同的结果，直到变形。(II) 如图6（b）所示。 一条边直接通向另一个内部节点x′，另一条边直接通向外部节点y。假设y在S中。我们必须将边带到外部节点y（“交叉调度”边）。为了理解为什么这是必要的，假设我们把边带到下一个内部节点x′。 由于x′··282G. McCusker等人/理论计算机科学电子笔记286（2012）273是一个内部节点，它是S的一个节点，由于S本身是一条通过它所有节点的路径，它最终将从x到达x′。然而，由于S中x之后的下一个节点是y，y在S的路径顺序中在x ′之前，因此y在x′之上。因此，由于所有的边都是渐进的，如果我们把边直接取到x′，我们最终将在y之下，因此永远无法到达它。• X•x′• Xy·.•x′(a) 顺序相邻的内部节点由两条边连接。(b) 顺序相邻的内部节点由一条边连接。见图6。 组成图这给了我们一个通过U + V + W的构图图中的唯一路径。□基于引理4.2，我们可以简单地将复合定义为通过复合图中每个节点的在情形（I）中，我们有两条从一个内部节点到另一个内部节点的边，引理的证明允许我们选择其中之一。然而，如果我们决定总是选择与传入边相对的传出边（这样我们就“穿过”节点），我们就有了从左右交替的方向接近内部节点的性质。这也构造了我们的复合，它们类似于[18]中的字符串图对于一个完整的组合示例，我们可以将图1（b）中左侧的原始示例调度与调度4→6组合在一起。这通过图5（a）、5（b）和5（c）中的示例再次示出。命题4.3给定时间表S：U→V和S′：V→W，它们的合成SS′是一个时间表U → W。证据关于嵌入的时间表和条件的数据很容易从定义4.1中得到，如（S1）所示。（S2）简单地说，一旦调度图的路径到达两边之一，它在交换之前保留偶数个节点在复合过程中，所发生的只是一些内部节点被删除，这可能导致同一侧的连续节点序列被连接起来。在路径的开始处，在W中，这只能是奇数与偶数的串联，从而根据需要产生奇数。一旦路径到达U，级联将是偶数与偶数，根据需要。因此，结果如下归纳的时间表的长度。□注4.4在引理4.2的证明中，人们可能想知道为什么我们永远不能有两条从同一个内部节点到外部节点的向外的边，或者两条从外部节点到同一个内部节点的向内的边。这种假设图7（b）和图7（c）显示了组成图的片段，尽管事实上它们永远不会出现。G. McCusker等人/理论计算机科学电子笔记286（2012）273283虽然其原因可以通过归纳法从（S1）和（S2）中推导出来，但是存在由所发现的不确定性的计算（或O / P -1计算）而产生的“不确定性”的普遍性在文献[5，12]。 观察到任意调度Sm，n：U → V，其中路径或U+V={p1，. . . ，pm+n}m可以被编译为以下文件：• v1为白色（绘制为），u1为黑色（绘制为·）。• 节点沿路径顺序交替显示白色和黑色。• U中的节点从上到下交替事实上，任何节点位于R2的垂直条两侧的渐进路径都是一个时间表。作为（S1）和（S2）的替代方案，着色方案通过着色，我们将每个节点的奇偶校验附加到其调度中。图7（a）显示了我们用这种方式修饰的图5（b）注意，当且仅当遵循该颜色方案时，满足（S2请注意，如果边从一侧移动到另一侧，则它们始终是有向的（这是因为对于图[1]，它是有向的）。 因此，如果所有pi都是black，且pi+1是其中n{pi，pi+1}是U或V。当并发执行时，内部节点的两个副本中的并发将在每个调度中精确地反转我们可以证明对于该复合材料层的中间层节点，如图7（f）中的节点。如果我们具有来自同一内部节点的两个交叉调度边，则它们两者都不能是n → ·，因为内部节点是两个组件表中的颜色不同;因此，这种情况是不可能的。对于同一内部节点的两个交叉调度边，也是如此。图7（d）和7（e）显示了具有颜色选择的假设碎片，以及用×标记的非法边缘。使用状态图的类似论点存在于游戏语义学文献;例如，[1，7]。5类别Sched现在我们得出关键的结果，即合成的结合性。这与身份的定义一起，将产生对计划类别的描述。命题5.1附表的组成是联合的。证据这足以表明，两种可能的三重组成是相等的。假设我们正在编写时间表Sl，m′m，n′′n，rU−→V−−→W−−→X（为了便于阅读，我们将其称为S、S′和S′′）。我们希望证明（S<$S′）<$S′′可变形为S<$（S′ <$S′′）。在不失一般性的情况下，我们可以定位S、S′和S′′，使得V的两个拷贝被识别并且W的两个拷贝被识别。这是一个3重组成图，图8中显示了一个示例。SS284G. McCusker等人/理论计算机科学电子笔记286（2012）273·◦·×）（n◦·◦（一）.·◦···◦.（b）第（1）款.）•（◦.（d）其他事项.····◦··.(c).◦·）◦（·.（五）◦）（·◦）（·（f）第（1）款见图7。 节点着色（SS′）S′′是通过首先移除通过V中的节点的扩展的“S”形，然后移除通过W中的节点的扩展的“S”形来实现的。对偶地，得到S（S′S′′）通过首先移除通过W中的节点的扩展的“S”形状，然后移除通过V中的节点的扩展的这些删除是对组合图的局部操作，因此结果必然相同。或者，根据引理4.2，复合（S<$S′）<$S′′和S<$（S′<$S′′）都是由通过每个节点U+V+W+X的3重组成图中的唯一路径（直到变形）给出。因此，（S<$S′）<$S′′和S<$（S′<$S′）之间括号的差别对应于我们是先从V还是先从W中去掉内边和内节点;两种选择都必须产生相同的路径。本质上，结合性是由于平面中并置的自然结合性。□我 们 现 在 开 始 研 究 附 表 的 类 别 。 这 类 的 对 象 是 一 个 有 限 的 集 合U={u1，. . . ，um}。态射m→n是时间表Sm，n：U→V的变形类。定义5.2模仿计划是“最交替”的计划可能的sub j e c t to the h e s h e s h e during l e a x iom s. 对于n∈N+，n的持续时间可以由点集P2n=U′+ Un上的路径描述来表示.p4k+1=u2k+1 ，p4k +2′2k+1′，p4k+3=u2k+2，p4k +4 =u2k+2×=uG. McCusker等人/理论计算机科学电子笔记286（2012）273285n从图形上看，这可以在图9中看到。可替换地，这些模仿调度可以通过具有所有{p2k+1，p2k+2}/pUnn和/pUn′来进行。下面的引理在附录A中被证明为引理A.1。引理5.3模仿调度In，n是调度合成的恒等式。286G. McCusker等人/理论计算机科学电子笔记286（2012）2731234·······························见图8。突出显示复合路径的三向复合关系图。请注意，由于我们必须在到达内部节点时总是在计划之间交叉，因此没有选择。• u1=p1p2=u′·p3=u′·p6=u′·p7=u′·.• u2=p 4• u3=p 5• u4=p8见图9。标识调度的前缀片段。定理5.4正自然数与图形表一起形成一个范畴，称为Sched，其中复合由定义4.1定义，恒等式领带都是模仿时间表我们将通过展示一个函子来证明SchedSched→给出等价性。设Sm，n：U→V是[u，v] ×R中的一个时间表;G. McCusker等人/理论计算机科学电子笔记286（2012）273287也就是Sched之箭我们构造一个函子C，它作用于对象作为单位元，并将一个n-调度函数e：[m+n]→ { 0，1}赋给Sm， n，其中.e：i›→0如果pi∈Lu1如果pi∈Lv在Harmer et al. [9]中，方案e：m → n对应于喷射eL：[m]n→[m + n]和eR：[n]n→[m + n]，其又对应于eL（x）

下载后可阅读完整内容，剩余1页未读，立即下载