痕量单体

在计算机科学中，痕量是一组字符串，其中字符串中的某些字母被允许换位，但其他字母则不允许。它概括了字符串的概念，不强迫字母总是按固定的顺序排列，而是允许进行某些重新洗牌。轨迹是由皮埃尔-卡蒂尔和多米尼克-福塔在1969年提出的，用于给出麦克马洪主定理的组合证明。轨迹被用于并发计算的理论中，其中交换字母代表工作中可以独立执行的部分，而非交换字母则代表锁、同步点或线程连接。轨迹单体或自由部分互换单体是一个轨迹单体。简而言之，它的构造如下：互换字母的集合由一个独立关系给出。这就产生了一个等价字符串的等价关系；等价类的元素就是痕迹。然后，等价关系将自由单体（所有有限长度字符串的集合）分割成一组等价类；结果仍然是一个单体；它是一个商单体，被称为迹单体。痕量单体是通用的，因为所有依赖同构的单体实际上是同构的。踪迹单体通常被用来模拟并发计算，形成进程计算的基础。它们是跟踪理论的研究对象。轨迹单体的效用来自于它们与依赖图的单体同构的事实；因此允许将代数技术应用于图，反之亦然。它们也与历史单体同构，后者在一台或多台计算机上的所有预定进程的背景下对单个进程的计算历史进行建模。

{displaystyleSigma{*}}表示自由单体。表示自由单体，也就是用字母表写的所有字符串的集合{displaystylephi_{D}:Sigma{*}tomathbb{M}(D)}。通常被称为自然同构或典型同构。

自然或典型这两个词是当之无愧的，因为这个变形体现了一个普遍的属性，这一点将在后面的章节中讨论。我们也会发现痕量单体表示为M(Σ,I){displaystyleM(ΣSigma,I)}。其中I{displaystyleI}是独立关系。是独立关系。令人困惑的是，人们也可以发现用换元关系代替独立关系（它的不同之处在于包括所有对角线元素）。