K-模的计算和Kan扩张技术

网址：http://www.elsevier.nl/locate/entcs/volume61.html17页K-模上的计算NeilGhani1和AnneHeyWorth2;3莱斯特大学数学与计算机科学系Leicester LE1 7RH，英国摘要Kan在集合范畴上的扩展为群、幺半群和范畴作用的计算提供了一个统一的框架，从而使许多不同的问题可以用广义的串重写形式来解决。本文利用Gr将这些技巧推广到K-代数和K-范畴上获得了计算K -模范畴上Kan扩张的基技术。1引言计算机代数：计算机代数软件包在数学和计算机科学中广泛用于解决组合问题，其本质是计算代数结构的商。这样的问题广泛地出现在整个数学中的群论，环，模等，和计算机科学，例如在方程推理[14]和Petri网的研究[28]。任何计算机代数软件包的核心是将代数结构表示为数据结构和用于计算商的算法。当前的软件包有两个主要缺点：i）计算限于那些代数结构和商，对于这些代数结构和商，数据结构和算法已经被构建到软件包中;以及ii）许多软件包限于有限结构，因为它们枚举商的元素。 因此，尽管有许多成功的计算机代数软件包用于群上的计算，例如Gap [12]和KBMAG [17]，但除了实现Todd-Coxeter类型算法的“向量枚举器”之外，几乎没有支持计算结构，例如环，模块和代数[23]。1 电子邮件地址：ng13@mcs.le.ac.uk2 电子邮件地址：ah83@mcs.le.ac.uk3 由EPSRC资助编号GR/R29604/01 Kan：计算机代数c 2002年由Elsevier Science B出版。诉 在CC BY-NC-ND许可下开放访问。2分类计算机代数：我们的长期目标是开发一个通用的计算机代数包Kan，支持不同代数结构中各种情况的计算我们的中心思想是使用广义形式的重写计算Kan扩展4，然后计算其他的条件，通过表达他们作为Kan扩展。 范畴论作为代数的元语言的使用可以追溯到Linton[22]和Lawvere[21]代数的研究一直是发展的中心分类理论[2]。我们在这里的主要贡献是观察到，这种元语言自然延伸，通过使用Kan扩展，以涵盖计算代数。使用重写来执行计算确保了，与枚举方法不同，我们的算法不限于nite结构。集合上的计算：在我们以前的工作中，我们把一些不同的计算问题统一为Kan扩张，其余域是范畴集。这些包括一些基本问题，计算群论，例如计算的介绍，陪集，轨道和诱导行动等Kan扩展，以及类似的理论monoid和范畴。群和幺半群的构造是基于自由幺半群函子，因此导致了基于广义形式的字符串重写的计算概念。这种方法的优点是，而不是实现许多不同的算法，并为每个算法提供正确性证明，我们只需要的正确性也被简化，因为结构被证明和他们的代表作为Kan扩展都是代数的性质，是-原因的商是简单的对称封闭的重写关系用于计算it. This工作总结在第2节，以便让读者熟悉自己与我们的一般方法。本文将我们的工作[4]推广到K-模、K-代数和K-范畴的计算中，利用Kan扩张，其余域是K-模的范畴KMods。K-模在表示论中特别有趣，而李代数、赫克代数、塞尔代数和弦代数是K-代数的广泛研究的例子。范畴方法并没有为这些结构发明新的计算范式，而是指出K-代数是K-模范畴KMods中的内部幺半群就像么半群是集合中的内部么半群一样。因此，可以通过使用与之前相同的Kan扩展来计算K-代数，但现在Kan扩展的余域将是KMods。 总的来说，代数结构从类幺半群结构到K-代数的变化是通过计算相同的Kan扩展，但在一个4 在本文中，“Kan扩张”是指左Kan扩张3更复杂的基础类别。在将K-代数的计算简化为Kan扩张与余域KMods的计算之后，我们转向这些Kan扩张的计算。从有限表示构造K-代数是基于自由环函子，这导致基于Gr的计算获得基础技术。背景资料：这种范畴理论和重写的综合是可以追溯到20世纪80年代末的一系列研究的一部分，当时人们发现，基于范畴的传统计算表示模型可以扩展到涵盖操作方面。这一领域的开创性研究集中在重写的分类模型的发展[30，29，18，25，13]。我们希望，通过导致软件的实际生产，这项研究将被视为范畴重写领域成熟的一部分。我们的工作与Carmody和Walters[6，7]的工作有关，他们提供了计算Kan扩展的Todd-Coxeter算法，但仅限于集合。这是由Rosebrugh在[10]中实现的。[4]的重写技术提供了一种枚举方法的替代方法，就像字符串重写提供了一种传统Todd-Coxeter方法的替代方法一样。总之，本文提供了一些理论和实践的见解。我们证明了在K-代数和K-模的背景下，不同的条件可以一致地建模为Kan扩张我们提供的证据表明，计算在不同的代数结构，可以通过改变相关的Kan扩张的余域。我们证明了Kan扩张到范畴KMods可以由yGr计算获得基础技术。因此，我们提供的算法计算典型的K-代数。还有一个问题需要解决，即本文是否适合理论计算机科学受众。虽然模块和代数可能不是这样的观众的标准票价，我们相信我们的方法是。当然，范畴论已经在理论计算机科学社区中广泛传播，为计算提供了元语言。事实上，很难找到一篇关于编程语言指称语义的现代论文，它不是用范畴方言写的。此外，重写显然属于理论计算机科学的范畴。我们相信，范畴理论的综合和重写，因此将感兴趣的CATS2002的参与者4˛¸第二节用群的例子来说明我们的一般方法，第三节介绍了K-模、K-代数和K-范畴，并说明了它们的基本性质。第4节推导了计算Kan扩张的算法，我们在第5节简要概述了一些例子。我们在第6节中总结了未来研究的计划。2集合计算我们说明了我们以前的工作Kan扩展集通过描述计算群论中的几个问题，我们对他们的解决方案2.1计算群论中的四个问题让我们：Grp！集合是从群范畴到集合范畴的遗忘函子，F是它的左伴随。定义2.1群表示grphXjRi由尼特集合X和尼特子集RF（X）组成。群G由群表示grphXjRi表示当且仅当G通过r0对r2R诱导的等价关系同构于F（X）的商.分类地，G由grphXjRi表示，当且仅当G是F（R）RzF（X）0其中r是由将r作为R的元素发送到r作为F（X）的元素的函数引起的，并且0是常为0的函数。无论哪种方式，G都是F（X）的商，对于p2F（X），它在G中的等价类记为[p]G.问题2.2给定G和元素p; q 2的群表示grphXjRiF（X），那么[p]G= [q]G是否成立？我们的第二个问题涉及陪集。定义2.3（陪集）设H是G的子群.陪集集集G=H是G的载体集通过等价关系g g + h的商，其中g 2 G和h 2 H。g2G的等价类记为gH一般来说，陪集G=H形成集合而不是群|乘法的明显概念在G=H的等价类上没有很好的定义。这个例子表明，一个人不能把代数计算的一般模型建立在coequalisers上，因为所有的对象都必须属于同一个范畴。问题2.4设H是G的子群，g1;g22 G. g1H= g2H吗我们的第三个问题是关于动作或G集的概念，并试图计算动作的载体集的商5定义2.5如果G是一个群，则G-集合是一个集合X，其函数GX！X（这里用并置表示）使得1x = x和（g1+ g2）x = g1（g2x）。动作的轨道是集合中元素的集合，可以通过对元素重复施加动作问题2.6让：GX！X是G集。 的轨道是X在等价关系xgx下的商，对于g2G。x 2 X的轨道记为[x].给定元素x0; x1 2 X，是否存在[x0]=[x1]的情况。最后，我们介绍了诱导行动的问题。问题2.7Let：GX！ X是G-集，f：G！的g0 是一个群同态。导出作用量=f是其载体为XG0与等价项之商的G0-集hgx;g0ihx;f（g）g0i（1）2.2商作为Kan-扩张人们可以为想要计算的每个商编写一个算法，以及相关的正确性证明。虽然这是可能的，但工作量使这成为一个漫长的过程，并增加了算法或其实施中出现错误的可能性。我们的替代方法首先将这些问题转化为范畴论。首先注意，我们可以把群G看作一个有一个对象的范畴范畴中的组成由群中的加法给出，恒等式是群的零当然，这种构造对任何幺半群都有效|群中逆的存在意味着关联范畴中的每个箭头都是同构。我们用G来表示一个群和它的相关范畴。以同样的方式，群同态形成函子。动作也是函子。特别是，给定一个动作：G X！X we de ne a functor：G！ 设置谁的动作将G的对象发送到X，并将每个g 2 G发送到函数（g）：X！X由（g）（x）= gx定义。G-集公理与函性公理精确对应。如果G是一个群，我们也用G来表示它的范畴表示，同态和作用也是如此。让我们转向我们的四个计算问题。我们从诱导行为的问题开始，因为它是最普遍的。回想一下，我们有一个G-集合：GX！ X和同态f：G！ G0 。诱 导 作 用 是 G0- 作 用 =f ， 其 载 体 是 XG0 在 等 价 关 系hgx;hihx;f（g）hi下的等价类，其作用是h0hx;hi=hx;h0hi. 先验地，这个特殊的引用并没有任何简单的分类解释，6函子F沿G的左Kan扩张是函子Lan G F：B！ C而行动做到了。 但是，请注意，： ）=ff：G！集他唯一的一个名字是：X！XG0=由y（x）=[hx;1i]定义，即映射将x发送到等价类hx; 1 i。的自然性就是等式1 导出作用量是方程1的商这一事实意味着导出作用量是具有这种自然变换的最小G0-集。 也就是说，在具有自然变换的G0-集之间存在自然双射：！ 自然变换=f）。 诱导作用量只是沿着f的左Kan扩张，记为Lan f。定义2.8（左Kan扩张）设F：A！ C和G：A！ B是使得存在自然双射Nat（LanGF; H）Nat（F; HG）。Kan扩张最初是在40年前发展起来的[19]，并且已经成为范畴论中的一个基本结构[8，24]。有许多左Kan扩张的替代公式，例如，当它存在时，Lan GaG：C A！CB. 上述讨论表明，诱导作用是Kan扩张|自然变换是附加的单位，双射性质是单位的泛性质。就其本身而言，将诱导动作表示为Kan扩展并不那么有趣。然而，有趣的是，到目前为止遇到的所有其他问题也是诱导动作，因此是左Kan扩展。引理2.9设1是有一个元素的群，且！G：G！1从G到1的唯一群同态。一个动作的轨道：G！集是沿的indu ce d行动！快来啊，拉！G.证据 诱导作用是一个商，（）下一页1同构于（）中选择。等价关系也是同构的：hgx;ihx;！G（g）i= hx; i.2引理2.10设H是G的子群。 如果是H在一个点集，则右（和左）陪集G=H同构于沿包含i的诱导作用：H！G，或者等价地，Kan扩展Lani。证据 诱导作用是1 G的商，它同构于G. 定义等价关系也同构h ; gi = h h; gih; hgi.2因此，我们有一种优雅而抽象的方式将计算问题编码为Kan扩展。读者可能会争辩说，既然我们所有的例子都是诱导行为，那么诱导行为就可以作为主要概念。事实上，诱导作用量正是函子的Kan扩张，7Z和codomain是1对象类别。由Kan扩展排序的额外的一般性在建模几个计算问题中是至关重要的，例如我们在第5节中提到的共极限和路径代数。subsection通过字符串重写计算Kan扩张的关键是将其表示为余A2ObA（LanFM）B = MAB（F A; B）其中是张量操作。在上面给出的例子中，M的余域是集合，因此MA只是一个集合，而张量运算是卡累利阿积。此外，范畴A和B是从图生成的，因此B（FA; B）是生成集B上的路的等价类的集合。因此（LanFM）B包含在自由幺半群（MA）的商中B）由B的关系和Kan关系hF（f）（a）;gihM（f）gi. 由于这些关系都是字符串，坎扩展作为一个商的自由幺半群之间的一组方程的话，即一个问题内的字符串重写形式主义表达。特别地，可以使用Knuth-Benzen完备化进行字符串重写以生成（如果可能的话）完整的字符串重写系统，并且因此确定（MAB）的两个元素何时表示Kan扩展中的相同元素。3K-模上的计算我们没有开发新的数据结构和算法来计算K-模、代数和范畴，而是将它们视为KMods中的内部构造，然后像以前一样使用它们进行计算。 为了做到这一点，我们定义了内部幺半群的概念|详情见[24]。定义3.1么半群范畴（C; ; I）中的么半群由C的对象X和映射e：1！X和M：X X！X使得明显的幺半群定律成立。给定一个幺半群（X; e;m），映射Z 7！XZ de nes单子对C的作用。一 个X-作用是一个X代数。例如，幺半群M是集合中的幺半群，而M-作用恰好是M-集合。在阿贝尔群范畴Ab中，Ab中的么半群是环R，而R-作用是R-模。在K-模范畴KMods中，幺半群是K-代数A，而A-作用是A-模。我们现在给出K-模等的更传统的定义。定义3.2（K-模）设K是一个 eld. 一个K-模是一个阿贝尔群加上一个标量8乘法：K！（并列）这样，k（g + h）= kg +k h（k1 + k2）g = k1 g+ k2 g（k1 k2）g = k1（k2 g）1m = m：前三个方程保证了它是一个双线性映射，并且通过阿贝尔群张量的泛性质，因此它可以与一个群同态：KA！A.第三个和第四个方程则构成一个K-代数.由于K-模是K-代数，我们可以把KMods定义为K -单子的Eilenberg-Moore范畴。更具体地说，定义3.3（KMods类别）给定K-模：K A！A：B！B，一个K-模同态是一个群同态f：A！B使得f（kg）= kf（g）。范畴KMods有作为对象的K-模和作为态射的K-模同态。K-模同态的条件可以写成AbK一一Kf fJJKBB它将K-模同态表示为K -代数同态。模块的分类方法给出了KMods结构的直接结果。首先，可以构造集合上的自由K-模引理3.4健忘函子U M：KMods！ 集合有一个左伴随的F M，它的作用将集合S映射到所有多项式k1 s 1++ kn s n的集合，对于si 2 S和ki2 K。事实上，KMods作为一个nitary代数理论出现，所以我们有下面的引理。引理3.5KMods是局部nitely可表示的，因此是完备的和余完备的.这个引理的一个推论是：如果存在模Kh的对，则K-模是唯一的jRi在哪里是一nite set和RM（）是一个nite集，使其成为下图中KMods中的coequaliserFM（R）RFM09其中r是通过将r发送到其在FM（）中的规范解释而定义的模同态，0是恒定为0的映射。 更具体地说，给出模KhjRi的表示，定义了FM（）上的等价关系f= Rh当且仅当f= h + k1r1++ knrn，其中ki2K和ri2R. 则集合论命题FM（）==R是K-范数，且y∈ ymodKhj Ri当且仅当FM（）==R.引理3.6KMods是一个对称monoidal闭范畴，如下所示单位是一个生成元上的自由K-模，即KK-模R A！A和RB！B！B表示为AKB是AB的商，关系式为r（ab）= rab = arb。指数[A; B]是A和B之间的K-模同态的集合。这个集合是一个阿贝尔群：（f+ g）x = fx+ gx; 0x = 0;（f1）x =（fx）1：标量乘K [A; B]！[A; B]由（rf）（x）= r（f x）给出。证据证明依赖于KMods作为交换代数理论的一个例子。注意，理论的交换性是必不可少的，例如群的范畴不是封闭的。 参见Borceux 2pp172或MacLane pp180 [3，24]。23.1KMods上的富集我们把K-代数表示为K-模范畴中的幺半群。回想一下，用群计算相当于把它们变成范畴，我们对K-代数也是这样做的。事实上，这是一个将monoidal范畴中的monoid映射到范畴的一般构造。事实上，我们得到的类别丰富范畴是指其根不是一个集合而是另一个范畴的对象的范畴。我们给出了一个基本的描述，并请读者参考[3，20]以了解更多细节。如果V是monoidal范畴，则V -范畴C由一个对象类jCj和对于每对对象的一个hom C（A; B）组成，其中hom C（A; B）是V的一个对象。此外，本发明还提供了一种方法，通过要求每个对象A 2 jCj，映射1 A：I来给出恒等式！C（A; A）in V合成是通过要求每个三元组的对象A; B; C2 jCj一个映射m A;B;C：C（A; B）C（B; C）来给出的！C（A; C）在V中。映射1A需要是用于组合的恒等式，并且组合需要是关联的。V -函子的定义类似。如果V =Sets，我们得到范畴的通常定义。如果V =Pre，我们得到有序范畴，而如果V =Cat，我们得到2-范畴。本文主要研究K-代数，它们是KMods中的幺半群，然后它们将变成一个对象，KMods-丰富范畴，简称K-范畴。10引理3.7设X是monoidal范畴V中的monoid。则X定义一个单对象V-富集范畴。 如果V是闭合的，则每个X动作a：XY！Y是一个V函子a：X！V.证据 证据是第2节中所作为类别的群体设X是V中的幺半群。定义V-范畴X有一个对象，并且X（;）= X。X的幺半群结构保证X是V-范畴.对于引理的第二部分，首先要注意的是，为了确保V是V-范畴，需要假设V是闭的。定义一个V函子a：X！我们必须将X的单个对象映射到V的一个对象，显然的选择是a（）= X。其余的证明是标准的，动作公理精确地转化为函子公理2虽然用K-代数计算只需要一个对象K-范畴，但正如我们之前所说的，这是过度限制的，一般来说，我们想用nitely表示的K-范畴进行计算。这些是基于路径函子的范畴的通常表示和上面给出的K-模的表示的综合。图的自由K-范畴是PK范畴其对象是它们的homes是PK（A; B）=FM（P）（A; B）其中A; B 2 Ob，P：Gph！Cat是路径函子，FM是自由模函子。更具体地说，PK（A;B）由形式为p = k1 w1 + +kn wn的所有多项式组成，其中k1;：; kn2 K和w1;：; wn2 P（A; B）。通常，nitely呈现的K-范畴是一个自由K-范畴与一组关系的商[26]。定义3.8（K-类别介绍）一个K-范畴表示由一个有限有向图和自由K-范畴PK的一组元素R组成对. 我们可以将演示文稿写成catK h jRi。所提出的范畴具有与相同的对象，其箭头是ArrPK在由R生成的关系下的等价类;即=R，其定义为f = R h当且仅当f = R h + k 1 p 1 r 1 q 1 ++ kn pn rn qn其中ri2 R; ki 2 K和pi; qi是其复合物被定义的PK的箭头。4K-模上Kan扩张的计算我们现在正式定义我们将用Gr计算的那些Kan扩张获得基础技术。定义4.1（Kan演示文稿）K-范畴的Kan表示是五元组P：= kanh ; ; R; M;Fi，其中11FFF2 Ob一i) 和定向（direct） nite graphs;ii) M：！KMods和F：！PK是图态射，对每个对象A2， M（A）由modK hA表示，RA i.iii) R是P-K上关系的集合。kanh;R;M; F是（M0;F0）的Kan扩张，其中M0 A！KMods和F0：A！B若A是cat Kh上的自由K范畴，Ri是B的K范畴表示，M诱导M0，F诱导F0.正如我们已经看到的，Kan扩张LanFM可以通过coend公式逐（LanFM）B=ZA2ObA马B（F A; B）在我们的背景下，MA和B（FA; B）都是初显的K-模。的本文首先给出了两个有限表示的K-模的张量积，因此我们认为生成元上的自由模是一个基本的数据结构，在它上面将出现三种形式的方程和重写规则：首先是与MA表示有关的方程，其次是定义B的关系，最后是定义实际Kan扩张的方程。因此，对于每个B 2 ObB和A 2 ObB，TA;B = FM（AP（F A; B））：Further de ne TB：=A2ObT A;B和T：=B2Ob T B. 或者，T A;B是所有元素k11 p 1 + +k nn p n的集合，其中k 1;：; k n2K，1;：; n2A和p 1;：; pn2P（FA; B）。我们将把元素p称为T的项，同时注意到并非所有这些元素的形式和都在T中定义。 此外，让;：T！Ob由（t）：= F（A）定义，(t)：= B对于t 2T A;B.它们分别是源函数和目标函数。如上所述，为了构造Kan扩张Lan FM，我们需要将范畴B的关系与定义M的K-模表示中的关系以及强制只有一个自然变换“从M到Lan FM<$F”的关系结合起来。给出三组关系式QTT，QMA2ObFM[A]和QRArrPK，定义Q = QT + QR + QM.我们通过将T嵌入到自由多项式环T+ = K[（+）]中来计算T中的$Q。其中=t A. 我们在幺半群（+ Arr）上选择一个容许良序>，即在（ + Arr ） 的 元 素 上 的 一 个 良 序 使 得 如 果 u 1> u 2 则 对 于 t; v2（+Arr），tu 1 v> tu 2 v。请注意，这种排序比我们需要的更强，但它在计算上是实用的，也更容易定义。T+的任意多项式q=k1u1++ knun的首项被定义为（+Arr）中的最大元素LT（q）= ui.ui在q中的系数是ki。我们注意到，对于多项式12F在T+中生成一个理想，我们可以将它们全部除以它们的首项的系数;因此我们可以假设首项的系数为1。定义4.2还原关系T上的Q由yf！QFKUQV当u（LT（q））v出现在f中，系数为k 2 K，其中i) q在QT或QM中，u = 1且v 2 P与 (q)= src（v），ii) q 2 QR，u 2 T和v 2 P和 (u)= src（q）和tgt（q）= src（v）。的完备、对称、过渡闭包！Q表示为$Q。T在$ Q下的等价类记为[t]Q。注意，如果t2 T B和t1！Qt2，thent22TB，并且该关系式表示加法和标量乘法.这给了我们以下结果。引理4.3F或Q，TB作为一个例子，限制的减少r！Q到模T B，是很好的定义，即如果t 2 T B，那么[t] QT B和T B =$Q是K-模。现在我们证明，我们已经描述过的由Q在项集合T上生成的约化关系捕捉到了Kan扩张。定理4.4设P：= kanh ; ; R; M;Fi是KMods上左Kan扩张的表示.德内i) QT：=F（a）M（a）（）代表所有人2M（src（a）），对于所有a2 Arr，ii) QM：=A2ObRA，iii) QR：= R。则由P表示的左Kan扩张是（LanFM;“），其中i) LanFM（B）是K-模TB =$Q，ii) LanFM（b）由 LanFM（b）[t]Q：=[tb]Q定义，其中b在Arr中，iii) “：M！LanFMF由“A（）：=[ 1F A]Q给出。证据需要验证如上所定义的LanFM是定义良好的K-函子。这可以从同余保持加法、标量乘和右乘的事实推导出来。要验证“是K函子的自然变换是很简单的。让a：A 1！A中的A2。设为M（A1）的一个元素.现在通过定义（LanFM）（Fa）（“A1（））=（La nFM）（Fa）（[1F A1]Q）=[1F A1p]Q=[p]Q其中[p]R=Fa，且“A2（Ma（））=“A2（[p]Q）=[p1FA2]Q=[p]，因此LanFMFa“A1 =“A2 我给所有的人都写了一封信：A1！A中的A2。通用型支柱完成了。设（E0;“0）是一对，130e0级 是来自B的K-函子！KMods和“0 是K-函子的自然变换。K-函子的一个新的自然变换：La nFM！因此，“=“0必须满足通信图：0的1M（A）“A1LanFA1z轴E0F（A）1FMF（A1）1M（p）JLanFM（p）JE0（p）JM（A）“A2LanFA2 E0F（A）2FMF（A2）0一个2¸2其都具有唯一的定义（p）=E0（p）（“0（1A）”）。 因此（La nFM;“）是普遍的。2通过对T和M进行以下观察，我们可以应用非交换Grobner基的标准方法[11，27]来获得一组p多项式Q使得$Q与$Q0重合 还有！Q0 是完整的。召回T是自由p多项式环K-模T += K[（+ Arr）]的子模。第二，我们可以去！Q+onK[（+Arr）]byf！Q+fkuqv，对所有k2 K和u; v2（+ Arr），使得uLT（q）v出现在f中，且收敛于k. 注意到T的限制！Q+与我们原来的关系相吻合！Q，如果！Q+在T+上是完全 的 ， T！ Q 在 T 上 是 完 备 的。 回 想 一下， 我 们 可 以 使 用Buchberger算法来尝试计算Gr在T+中获得Q的基础，并且thus和Q0 苏CH！Q0+是完整的。此外，在对Q执行Buchberger算法期间，没有计算将产生不是T+的子模T的 成员 的 多 项式。因此，如果在T+中应用于Q的Buchberger算法终止，则给出Grobner基Q0，则Q0是T+ArrPK 的 子 集 ，所以！Q0 是弱定的且收敛于T。这给了我们以下结果。推论4.5（Grobner基理论的应用）Gr可以使用obner基来计算该类型的左Kan扩展。给定Q，我们可以使用Buch- berger算法的非交换版本以通常的方式[27]来尝试计算T +中的Grobner基。辅助电源Q0 一个Grobner基，则Q生成T上的收敛约化关系，Kan扩张由下式给出：i) LanFM（B）：=irrQ0（TB），ii) La nFM（b）：t7！对于LanFM（B）中t，PK中p，（p）= b和src（p）=（t），iii）“A（）：=.其中irrQ0（t）是t通过y的重复约化的不可约结果！Q0 irrQ0（TB）是T B中关于TB不可约的所有项的集合，！Q.2““145示例我们完成的文件，显示我们的计算Kan扩展可以用来解决一些重要的数学研究人员的问题。第一部分是关于K-代数的表示，我们把它表示为单对象K-范畴。因此，K-代数表示是其图具有一个顶点的K-范畴表示。给出了上的自由K-代数的一个K-代数表示catKh; Ri，是不是[] B =[] B？例5.1（代数表示）设A是平凡K-范畴，B是K-范畴B。让F：A！B是唯一的函子，设M：A！KMods将A的对象映射到K-模K。然后计算Lan FM等价于计算由K[X]== R表示的代数，其中X是中的边的集合。具 体 地说，当函子Lan FM应用于B的对象时，给出了一个同构于代数（幺半群环的商）K[X]== R的K-模。在箭头上，函子给出了模的自同构，它定义了模在自身上的右作用LanFM（b）p = pb。这给出了代数的乘法 自然变换“选出单项式，它是代数a的乘法单位元，即。 “A（1）=[1X]R。图上的图代数的构造是表示论中的一个基本这可以建模如下。注意，这个例子需要函子的Kan扩张，其域/余域有多个对象。例5.2（路代数）设B是路代数，即图上的自由K-范畴.设顶点与而是一个空的边集，F是包含。让M：A！KMods将A的每个对象映射到K-模K。然后Kan扩张LanFM定义了B上的R代数.代数上的自由模可以计算如下。例5.3（代数上的自由模）设A是平凡K-范畴，M将它映射到生成元集合上的自由K-模。设B是K-代数，B是单对象K-范畴。设F是从A到B的函子。则M沿F的Kan扩张给出上的自由B-模。陪集的构造是整个代数的基础。我们已经在群论的上下文中看到了它，下面的例子构造了K-代数的陪集。请注意，结构如何仅通过将集合上的monoidal结构的单位即1替换为KMods上的monoidal结构的单位即K的丰富来改变15例5.4（K-代数中子代数的陪集）设A和B是K-代数，看作是一个对象，K-范畴在KMods上丰富。设F是A到B的包含。然后令M将A的对象映射到K-模K，并将所有箭头映射到单位K-模态射。然后LanFM将B的单个对象映射到A在B中的陪集的模。众所周知，范畴中的上极限是沿着函子到终结范畴的Kan扩张。丰富这个构造允许我们计算K-模的余极限。为了简单起见，我们处理上积，即直和，并注意到这个例子需要函子的Kan扩张，其域不是单个对象K范畴。[24]第二十四话例5.5（余积/K-模的直和）设A是一个有n个对象的离散范畴，B是平凡的K-范畴。设F是从A到B的唯一函子，M将A的对象映射到K-模M1;：;Mn.然后Kan扩张LanFM计算K-模的余积/直和M1+：：+Mn最后一个例子是诱导模例5.6（诱导模）设A和B是表示为一个对象K-范畴的K-代数，设F：A！B. 设M把A的对象映射到一个K-模M（A）上，把箭头映射到这个K-模的自同态上，则M定义为一个右A-模。M沿F的Kan扩张给出了F在M上诱导的右B-模。详细地说，Lan FM（B）是K-模，并且LanFM（b）：Lan FM（B）！LanFM（B）给出了K-代数B的元素在LanFMB上的右作用。自然变换“A：M（A）！LanFM（B）确认LanFM（B）是诱导模。6进一步工作我们已经证明，范畴理论，特别是Kan扩张，提供了一个表达元语言描述各种涉及K-模，K-代数和K-范畴的概念。我们还展示了如何Grobner基地技术可以应用于计算这些Kan扩展，从而开辟了道路，他们的正式实施的一部分，计算机代数包。我们认为，在Kan扩张的水平上的一致性的统一，以及在不同的代数结构中的计算的统一，通过改变的丰富性，是一个优雅的理论见解，也将显着提高软件的质量和可靠性。今后的工作主要集中在算法的实现和进一步的理论发展两个方面。当前的实现是用Gap编写的函数集合，需要进一步开发。Kan扩张函数与更快的Grobner基的接口16程序是提高效率的一种可能性我们正在与代数学家讨论我们的算法，以便得到更多的例子来测试，特别是我们想进一步研究计算张量积作为Kan扩展的可能性。在理论方面，我们考虑了一些增强：在重写中使用模块化的结果来整合所使用的重写的不同概念; 2使用自动机理论来给出计算的标准形式的语言理论描述; 3优化Knuth Benchmark过程以获得完整的重写系统。总的来说，当然还有更多的工作要做。引用[1] F. Baader 和 T. Nipkow ： Term Rewriting and All That 剑 桥 大 学 出 版 社（1998）[2] M. Barr 和 C. Wells ： Toposes ， Triples and Theories ， Springer ，Grundlehren der Mathematischen Wissenschaften Series no.278（1985）[3] F. Borceux：Handbook of categorical algebra，Encyclopedia of mathematicsand its applications，Vol. 50，p. xv，345p，Basic category theory/ FrancisBorceux Cambridge：Cambridge University Press，1994.[4] R. Brown和A. Heyworth： Using Rewrite Systems to Compute Kan Extensionsand Induced Actions ofCategories，Journal of Symbolic Computation，vol.29p5- 31（2000）[5] M. R. Bush ， M. Leeming 和 R. F. C. Walters ： Computing Left KanExtensionsJournal of Symbolic Computation，vol.11 p11-20（1997）[6] S. Carmody，M. Leeming和R. F. C. Walters：The Todd-Coxeter Procedureand Left Kan ExtensionsJournal of Symbolic Computation ， 19 p459-488（1995）[7] S. Carmody和R. F. C. Walters：计算A中自由范畴上作用的商。卡尔博尼湾C. Pedicchio，G. Rosolini（eds），Category Theory，Proceedings of theInt.Conf. Como ， Italy 1990 年 7 月 22-28 日 vol.1144 of Lectures Notes inMathematics，p131-56，Springer-Verlag（2000）[8] E. J. Dubuc：Kan Extension in Enriched Category TheorySpringer LectureNotes in Mathematics，vol.245（1970）[9] D. B. A.爱泼斯坦和J. W. Cannon et al：Word processing in groupsJones andBartlett，Boston（1992）[10] M. 弗 莱 明 河 ， 巴 西 - 地 Gunther 和 R. Rosebrugh ： User Guide for theCategoriesDatabaseandManualanonymousftp：//sun1.mta.ca/pub/papers/rosebrugh/catdsalg.dvi，texand/catuser.dvi，tex（1996）[11] R. F r oberg：AnintroductiontoGr02The Dog of the Dog（1997）[12] GAP 小 组 ， 《 GAP { 组 、 算 法 和 编 程 ， 第4版 》 ， Aachen ， StAndrews，（1998年）（http：//www-gap.dcs.st-and.ac.uk/gap）。[13] N. Ghani和C. Luth：MonadsandM odularRewritingPr oc. 范畴理论和计算机科学1997，计算机科学讲义，Springer-Verlag 1290 p69-86（1997）[14] Goguen和T. Winkler：介绍obj 3，技术报告SRI-CSL-88-8，SRI（1993）17[15] A. Heyworth：Groebner Basis Techniques for Computing Action of K-Categories，Proceedings of Category Theory 2000 16-22 July，Como，Italy，105-113（2000）[16] A. 嘿沃斯和J。斯内尔曼：莱斯特莫杜勒斯大学obner基地，预印本（2001年）[17] D. F. Holt：Knuth-Bennett in Monoids，and Automatic Groups，Universityof Warwick（1996）.[18] C. B. Jay：Modelling Reduction in Conuent Categories计算机科学中范畴的应用P143-62 C. U. P. （一九九二年）[19] D. M. Kan：Adjoint Functors，Trans. Am. Math.Soc.87 p294-329（1958）[20] G. M.凯利：丰富范畴理论的基本概念，伦敦数学学会。C.U.P.第64号（1982年）[21] F. W. Lawvere：代数理论的功能语义学。Nat. 请讲第50卷第869 -872页（1963）[22] F. E. J. Linton：Some Aspects of Equational CategoriesProc. of Conferenceon Categorical Algebra p84-94 Springer-Verlag（1965）[23] S. A. L