《局部序空间中双映射及双同伦的并发建模》-斯特凡·索科洛夫斯基-2002-Vol.52 No.2

《理论计算机科学电子札记》52卷第2期（2002）网址：http://www.elsevier.nl/locate/entcs/volume52.html23页po-空间和局部po-空间斯特凡·索科洛夫斯基波兰科学院计算机科学研究所，ul. Abrahama18，81-825Sopot，Poland电子邮件：stefan@ipipipan.gda.pl。摘要本文研究了[局部]序空间中双映射及其双同伦的一些不同概念.讨论了它们在并发建模方面各自的优缺点。这应被视为有助于使这一办法的基础具有某种秩序内容1介绍21.1基本概念和符号32全局偏序空间42.1双路4的固定端双同伦2.2双同伦等价问题52.3基本偏序集72.4基本偏序集9的泛函性2.5弱转向回撤143局部po-spaces 163.1Long dipaths 163.2一致双同伦183.3长导程数的一致不变性193.4有关概念的讨论21鸣谢. 22参考文献221 这项研究得到了丹麦奥尔堡大学为期3周的访问奖学金的支持，波兰国家科学研究委员会（赠款8 T11C 037 16）和计算机科学研究所PAS。c 2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。索科洛夫斯基21介绍正如许多作者所指出的那样，几何和拓扑方法在并发过程理论中具有潜在的应用（有关综述和丰富的参考书目，请参见Fajstrup，Goubault和Raussen的[1]一个家庭的并发进程的可能执行在这个框架中建模为轨迹（dipaths）在其可能congurations的空间。过程对资源的竞争可以被描述为这些空间中的“洞”。现在，轨迹的小变形，不涉及“跳过”孔，占执行顺序的无意义的变化，而不重新安排资源的使用这种无害的变形产生了同伦拓扑概念的类似物。原则上，对这种洞和变形的研究应该类似于用代数拓扑工具对拓扑空间的研究。然而，并发的几何和代数拓扑理论的基础 虽然po-space作为夜间运行进程的家的概念（参见，例如，[1]由Fajstrup，Goubault和Raussen）似乎是适当的，并successently很好地理解，同样的只是部分真实的本地po-spaces服务于在nitely运行的进程。 事实上，就在一年前，我们觉得它需要调整（参见。[2]Fajstrup和Sokolowski）。在态射方面有更多的疑问。序空间X中的双路（有序区间~I到X的连续单调映射）的自然概念不容易推广到任意序空间的双映射适合于通常的同伦（或更确切地说是异伦）研究。po-空间的双同伦等价的自然概念似乎太宽容了，因为它标识了太多的po-空间，从计算的角度来看，这些空间最好分开。最重要的是，双同伦偏序集的自然构造（cf。[7]由Sokolowski），对应于同伦群在代数拓扑，未能函。在局部po-spaces中，情况甚至更不稳定在X中的长导径的概念（cf.[5]由Raussen），这是一个连续的和局部单调的映射的非负实数R0到X，产生了一个分类的这种dipaths到nite对应于终止计算（例如，死锁）和在nite的那些对应于在nite计算。真不错但也有一些nite长双路与nite长双路同伦的例子这是最不受欢迎的，甚至是不可接受的，如果双同伦的概念应该有计算意义的话。这份报告提出了一些问题，并在某些情况下，提出了限制的概念，旨在保持问题。但似乎没有希望有一个单一的二映射概念和一个单一的双同伦概念，很好，很简单。我们最好习惯于处理许多类别的双映射，每一个都有一个目的，索科洛夫斯基31对别人没用。1.1基本概念和符号本报告涉及po-spaces，即，拓扑空间X的偏序是X X的子集闭的。在大多数情况下（不总是），假设po-space是指向的，即，以具有关于该阶的可分辨最小点序空间的指向性对理论没有太大的影响，它只是简化了一些公式。这个报告也涉及局部po-spaces。从技术上讲，这是一个复杂的概念，参见。[2]由Fajstrup和Sokolowski。但就本报告而言，局部po-空间是一个拓扑空间，它有一个由po-空间构成的开覆盖，并且在松散的意义上，这些开集上的局部偏序重合2。在本说明中，以下po-space用于辅助目的：我|区间[0：：1]的标准拓扑和离散顺序：s s0（d）fs=s0~我|区间[0：：1]具有标准拓扑和标准顺序。r10的|具有标准拓扑和标准序的非负实数集[0：：+1）。[局部] po-空间之间的二映射总是指这些空间之间的连续和[局部]单调映射。有时候，额外的限制会被施加在双映射上，从而产生[局部] po-空间的全范畴的子范畴。双同胚是具有逆双映射的双映射。从[局部] po-空间X到[局部] po-空间Y的双同伦是从IX到Y的连续和[局部]单调映射。同样，有时会对双同伦的一般概念 两个二向映射;：X！Y是双同伦的（记为"）i，存在从X到Y的双同伦H，使得“= Hh0;i和=Hh 1; i.一个偏序空间X中的一条导路是一个二映射：~我！X. X中的偶径集记为D1X.在点po-space X中的初始偶路的集合是IXd=ef n2 D1X0 = 0o其中0是X中的最小点。有向路模型是并发进程系统的一种有限计算。它的单调性说明了时间只会向前流动的事实。它的连续性排除了一种“心灵传输”，这种“心灵传输”会突然将这样一个系统的状态改变为一种完全不同的远程状态。2 这一定义的复杂部分是对这一巧合的精确表述，以及对特定掩护的独立性的精确表述。索科洛夫斯基42整体序空间2.1双路的固定端双同伦在我们主要关心的点序空间X中，任何两个初始的有向路都是互同伦的。为了证明这一点，achdipathtoaconstntdipathtd=ef0，并将它们粘在一起，明显的方式。这表明，无限制的双同伦是无用的分类的dipaths。一条转向路的端点在整个双同伦中的移动必须以某种方式受到限制。Fajstrup、Goubault和Raussen在[1]中采用了一种非常一般的方法，其中双路的双同伦的概念由任意子集AX和双同伦保持双路的端点在A3内的要求参数化。 我将假设A是一个单例集，但我将允许每个异同伦有一个不同的单例集限制：1定义：X中双路的xed-ends双同伦是连续单调映射H：我 - 我！ X使得对于所有s 2 I，H hs; 0 i = H h 0;0 i和H hs; 1 i = H h 0; 1 i（即， 保留了二径的端点 xed）。双径路和是xed-ends双同伦的（记为by'd），如果存在一个xed-ends双同伦H的双路使得=Hh 0;i和=Hh 1; i.当然，两个双径是xed-ends双同伦的必要条件是它们有相同的端点。因此，X的每个可达点至少有一个闭端双同伦类.如果X中有洞，则双路的xed-ends双同伦类的集合可能更大。在计算上，xed-ends双同伦标识了并发系统的执行，其中共享资源以相同的顺序分配给特定进程。这对应于以相同的方式绕过po-space中的洞。注意，双路的xed-末端双同伦的定义并不容易推广到po-空间的其他双映射的双同伦，甚至不容易推广到po-空间的其他双映射的双同伦。pointed po-spaces.特别地，在其他的序空间中，没有明显的对应要求，即路的端点是固定的，因为可能没有（或有很多）端点。指向性的性质在计算上是自然的，因为它解释了一个从定义良好的初始状态开始的并发过程系统，但是最大点的存在会排除许多有用的例子。另一方面，由于两个3实际上，X有两个子集，分别限制了导路的为了简单起见，我假设前一个设置为f0g。索科洛夫斯基5Q我0从一般偏序空间X到Y的双映射不一定彼此同伦，一般双映射的同伦分类也不一定像双路的同伦分类（无x端）那样无意义。目前，我们需要忍受这样一个事实，即有向路的同伦分类不同于其他有向映射的同伦分类。尤其是，这意味着“但不是另一个方向。2.2双同伦等价定义两个（局部）po-空间X的双同伦等价'和Y作为一对二向映射XY，使得 'id Y.但目前还不清楚两个po-空间的双同伦等价是否有任何计算结果。考虑到在第二节中讨论的对双路双同伦概念的限制。2.1，两个（局部）po-空间可以是双同伦等价的，在它们的偶路集上没有任何自然关系，甚至直到偶路双同伦。2例如考虑图14中带有一个正方形孔的正方形和瑞士ag。很容易认识到，它们分别与图1中的“薄”序空间2（cf.[3]由Gaucher）。现在，一个双同伦可以收缩右手边的po-空间中的两个直线段，表明原始的po-空间是双同伦等价的，即使其中一个允许死锁，而另一个不允许。这是一个我们肯定不想要的结果，因为这是我们在并发中应用同伦考虑的一个很好的例子。另一方面，单方孔po空间中的路表现为这与瑞士的不同。 这表明，在没有进一步要求的情况下，po-空间的双同伦等价可能没有更深的计算意义。2例2中提到的特殊异常可以通过以下方式排除：要求所涉及的双映射和双同伦是严格的。 对于偏序空间X和Y，'：X！ Y是严格二映射当且仅当'是连续的，8x;x0 xh2x1;2y1iifx=y>>2R r rI@@6R1X0R r rAKAAKAR r原名R1X12图9.第九条。优向映射双同伦等价序空间的不同基本偏序集。现在提醒你一句尽管限制型双映射范畴具有一些好的性质，但它们仍然不够好。也就是说，po-空间的基本偏序集，如果是优向映射双同伦等价的，则不一定是同构的。请考虑以下示例：17例如对于任何0t1，定义如下的位置空间Xt：第八条（1）款（0）项X的&t0X（t）_>（2）（x= 0y > t）_不9>>（二）（四）Xd=ef >：（3）（x >ty= 0）_（4）x=y > t;>=（1）>|{tz}（三）请注意，X0仅由三条直线段组成。 现在来一对'的dimaps X0X1 By2'hx;yid=efhx; y ih 0; 0 i如果0X2&0X2hx; yi d=ef >>h0;2y1iifx=0y>2H2x 如果x > 2& y = 0，则为1; 0i>Q我1索科洛夫斯基15很容易看出，'和都是较优的二向映射;并且在'和idX0之间存在一个super二向映射dihomoto 以及另一个在X和IDX1之间的超二次映射。另一方面，在一项研究中，2相应的基本偏序集是不同的，如图2所示9.第九条。2这意味着我们的双同伦等价概念还没有被重新定义。够了。索科洛夫斯基1662.5弱双径回缩条件（1）在Def.一个上二次映射的9并没有给各种的系统的分配。如果假设存在这样的系统分配，则二向映射变成弱二向路收缩：18定义：一个二维图：X！ Y是弱的偶径收缩，(i) 这是通常意义上的共收缩，即，存在一个dimap：Y！X，使得X'= id X，并且(ii) 满足以下条件：82I1X 82D1 Y6）2006年Q"Q vq“我的天6Q所以弱的重径收缩是点上的余收缩，几乎是重径上的收缩。在一个相关的报告[4]中，Martin Raussen给po-space分配了基本范畴，它似乎与基本po-set有很多共同之处。特别是，马丁指出，分配是函的连续和单调收缩的dipaths。后来，他认为，从地图上收回分歧是如此之大的要求，以至于这个概念毫无用处。这里所提出的弱转向回撤可能是一条出路。另一方面，回缩在模拟计算机系统中扮演着特殊的角色，因为它们具有实现的优势;共回缩对应于编码，而回缩对应于解码。19命题：每一个弱导径收缩：X！Y是上二映射。因此，函数1'是广义单调函数，1是从弱收缩的po-空间到单调函数的po-集的函子。弱的双径收缩总是内射的，一般来说，不是满射的。QQQ索科洛夫斯基1720例如一个正方形注入到一个更大的正方形中是一个弱导径收缩。由于1将一个单元素分配给一个正方形，因此由这种注入引起的单调函数就是单位元。填充洞（例16）是弱的转向回缩;实际上，其逆定义为：hx;yid=efhx; yi if x 1=2h1=2; yi if x 1个=2个请注意，它本身不是一个super：dimap，def。第18章不需要你去做因此，可能没有单调函数诱导的基本偏序集的逆有向映射的弱有向路图10呈现了将由正方形的两个面和对角线组成的po空间嵌入到具有邻近其边缘的两个孔的正方形中。这是一个优越的二向映射，但不是一个弱的二向径收缩。实际上，逆二向映射必须将整个E-区域收缩到初始点A才是单调的;这与“是点上的收缩”的要求相矛盾。这个例子表明，由上向映射诱导的单调函数该函数在图中给出。十一岁2B C“ -一个DX Y图10个。一个不是弱向径收缩的上向映射B CDI@@6A1X1' -H KLAKAAKAF GKAAE1Y1'A = E1'B = H1'C = K1'D = L见图11。由图1的上向映射诱导的非满单调函数。10个。HFKEG L索科洛夫斯基183局部序空间MartinRaussen [5]提出了一个处理长路径的框架|也就是说，R0到局部po-spaces的双映射，参见第一节的定义3.1| and their dihomotopies. 特别是，他区分了有限制的分歧（可扩展和不可扩展的nite）和没有限制的分歧（不可扩展的nite）。这两种长路径的作用是不同的。 具有极限的那些对应于成功或不成功终止的计算。那些没有限制的模型在nitely运行的进程。如[5]中所指出的，具有极限的双径可以与不具有极限的双径同伦|参见下面的实施例21。这是不幸的，因为一个计算上非常关键的区别逃脱了并发进程的代数拓扑的形式主义。马丁解释说，这种情况不可能发生在立方体复合体中。而不是限制类的局部po-spaces考虑，我提出了一个批判性的眼光在经典概念的同伦：一个任意的dimap从I X到Y。当双同伦的概念应用于长的双路时，如在[5]中，不清楚双同伦变形应该如何表现“In the nity”。我的回答如下：最好是连续的那里也是。 更确切地说，长路的异同伦最好是一致”映射|如在SEC。3.2以下。正如在续篇中所证明的，一致同伦永远不会将一个不间断运行的进程与一个终止的进程等同起来。均匀性通常是在度量空间而不是拓扑空间的背景下研究的，至少就我对它们的了解而言是这样。 我感兴趣的领域是紧局部po-spaces11。因此，我推广了均匀性要求，使得它不需要度量12。3.1长距离局部序空间X中的长导路是一个二向映射：R 0！X.它在X上可能有极限，也可能没有极限。一个长的分流是：如果x=li mt，则可扩展！+1T存在并且它不是最终点（即，存在一个从x开始的非恒定的二径）;niteinextendibleifanx=limt！+1t存在且为最终点;在黑夜里，如果没有限制，就无法延长！+1to es不存在。nite inextendible long dipaths对已终止的执行进行建模，无论是成功执行还是处于死锁状态。在夜间不可延长的长路径模型的执行，永远进行。可伸长的长径线11 这是一个比nite立方复合物更大的类。12 正如一位裁判所指出的，一致性是在一般拓扑空间中研究我不知道这些研究是否与Def的概念有关。22索科洛夫斯基19在计算中没有对应物，因为它们的“长度”在重新参数化后可能会消失。一个死锁的执行（nite inextendible）可能与一个非纯运行的（in niteinextendible）是异同伦的，甚至在一个紧凑的局部po-space中也是如此：21例如以在夜间地带R0 我并引入一个非标准偏序：hx ;yi hx;yi（d）fXx &yy&X yX y1 1 2 2 1 2 1 2 1 2 2 1上述合取中的最后一个条件意味着向量hx2; y2 i比hx1; y1 i“陡”。证明这是一个偏序，并且在标准拓扑中是封闭的，是很简单的。注意，相同高度的两个不同点ht，hx1;yi和hx2;yi，其中x16=x2，may仅在y=0时是e相关的。通过点hx; yi且y> 0的方向路径最终必须收敛到水平轴y = 1上的一个点，其点是不可比较的。图图12给出了一些长距离的例子。它也暗示了在许多会聚到水平轴上的一点的nite长的重径之间的一个重同伦t = 1，沿水平轴方向的单根长导程t = 0。形式上，这个双同伦由下式给出：H：我R 0！R 0IHh;tid=ef不1+（1）t（一））t;1+（1）t这是一个非紧的全局po-space。它可以被包裹在一个圆柱IS1上，这是一个紧的局部序空间，而不会失去nite和innite长路的不受欢迎的同伦性。2Hh0; i图12个。nite与inite间的异同伦从现在开始，X将表示紧局部序空间，而和将表示长的路。“”“”“！！！！！！！！”“那是什么？！“的“”！！！““！！“啊！“啊！！！“的！““啊！！Hh1; i索科洛夫斯基20000用S1表示圆net2i0t1o. 以下是两条长长的不同的道路8 0，使得8y2Y8s;s02Ij s

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