反应网络的化学组织和片段之间的关系及化学组织理论的研究进展

理论计算机科学电子笔记272（2011）19-41www.elsevier.com/locate/entcs碎片和化学组织Peter Kreyssig，Peter Dittrich1生物系统分析弗里德里希·席勒耶拿德国耶拿peter. uni-jena.de，dittrich@minet.uni-jena.de摘要我们描述了反应网络的化学组织和该网络的片段的化学组织之间的关系的一些方面。 猜想是可嵌入的片段在分子的（可行的）组织中，是片段的（可行的）组织。我们证明这是一个特定类型的反应网络。然而，分段总是可以改变的，使得结果对所有网络都有效。 当然，这是有代价的，即一个不那么粗粒度的片段系统。 为的情况下，我们不改变的碎片，我们给出的例子，声明是真的和反例，它不是。此外，我们提出了一些有趣的例子来说明我们的发现和进一步的问题。关键词：片段，基于规则的模型，模型简化，反应网络，反应网络，化学组织理论，建设性动力系统1引言反应网络是指一个对（M，R），其中M是一个集合，R是Pmut（M）× Pmut（M）的子集。这里Pmult（M）是M上的多重集的集合。我们称M分子种类的元素和R反应的元素类似于化学概念反应网络也可以用Petri网或多集重写来描述反应通常没有明确给出，而是隐含地作为规则，这意味着类似的反应被分组在一起。为此，我们写（M，R），并将其称为基于规则的模型，与基于反应的模型（M，R）形成对比。我们的R可以看作是覆盖R的R的子集的集合。然后我们说R中的一个元素与它所包含的反应相匹配。对于一个对应的（M，R），产生（M，R）的映射称为t。我们使用κ语言[ 2 ]来形式化基于规则的模型，并以简洁的方式写下示例。一般而言，人们会认为基于规则的模式更可取[1]主要感谢Je r omeFeret和TatjanaPetr ov，他们向作者介绍了碎片的概念。我们感谢德国研究基金会（DFG）资助DI 852/4-3的资金支持。1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.04.00320P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）19˜设（F，R_∞）为碎片与反应的反应网络因为它允许不写下所有的分子种类和反应，而只是给出模式[1]。然而，化学组织理论是为基于反应的模型制定的，而碎片的概念是为基于规则的模型定义的当它们描述相同的反应网络时，我们将在模型之间自由切换。碎片的概念是由Feret et al. 在[5]中。其背后的思想是使用抽象解释框架中的技术从基于规则的模型（M，R）中导出简化或粗粒度的模型。它由一组观测量F和一个离散系统组成，即一组描述它们浓度的常微分方程。这个新模型携带了大量关于原始模型的信息由质量作用定律给出的常微分方程组（M，R），但可能小得多。F的元素被称为碎片，因为它们可以被认为是M中分子的部分或组分。片段的显著特征是它们对于差异语义的可靠性，这可以大致概括如下。假设（M，R）的质量作用动力学，片段的浓度作为分子种类浓度的线性组合给出。特别是，健全性意味着分子物种动力学的固定点会产生碎片动力学的固定点。在[3]中给出了化学组织的定义。 粗略地说，一个子集O如果O中没有反应产生O中不含的分子（闭合条件），并且可以选择正反应速率，使得O中的分子量不会下降（自我维持条件），则M的结构是一种组织。定理42[3]存在于分子物种动力学定点的M分子形成了一个组织。我们感兴趣的情况下，减少动态的片段是一组化学常微分方程，因为我们然后能够计算组织的片段。在产生简化动力学的片段之间进行重新分配。 如前所述，片段的可靠性意味着出现在定点中的组织中的片段形成（F，R）的组织。因此，我们推测，这不仅适用于在定点中发现的组织，而且适用于所有组织。这个猜想在这里被证明为某一类反应网络。给出了该猜想的一个反例，并通过一个例子证明了我们的结果是可以推广的。第2节和第3节简要概述了我们需要的组织和碎片理论的部分内容。第4节包含了我们的猜想的一个更正式的版本和它的特殊情况下的证明。在第5节中，我们给出了一些例子。最后，我们陈述我们的结果的一些好处，并提到开放的问题。2化学组织理论我们总结了化学组织理论所需的概念[3]，[6]。定义2.1设M是一个集合，R是Pmut（M）× Pmut（M）的子集。 这对（M，R）称为反应网络，我们称M为分子集合，RP. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）1921m∈Mm∈M一系列的反应。我们为本文的其余部分确定了一个反应网络（M，R）。通过将反应（l，r）∈R应用于M上的多重集，我们意味着用子集r替换子集l。我们假设所考虑的多重集总是足够大对于（l，r）∈R，我们也记为l−→r或lmm −→其中lm，rm∈N0分别表示m在l，r中的重数这类似于化学符号。此外，（l，r）的支集和乘积是supp（l，r）：={m ∈ M |l m> 0}，prod（l，r）：={m ∈ M |r m> 0}。设A是M的一个子集。我们通过设置来定义RAR A：={（l，r）∈R| supp（l，r）<$A}.化学计量矩阵SA∈R|一|×|RA|因为A由下式给出：（S A）a，（l，r）= r a− l a， a ∈ A，（l，r）∈ R.定义2.2M的子集A是闭的，如果对于所有反应（l，r）∈RA，我们有prod（l，r）<$A，即如果（A，RA）是一个反应网络。A是封闭的意味着通过将RA的反应应用于A上的多重集我们不能得到A之外的分子。定义2.3M的子集A是半自保持的，如果对于每个a∈A，（l，r）∈RA且la−ra>0reisa（lJ，rJ）∈RA且raJ−laJ>0.半自我维持意味着如果一个反应应用程序破坏了一个物种，就会有一个反应产生这个物种。定义2.4 M 的子集A是自保持的 ，如果存在向量v ∈ R|RA|有严格正项使得S A v∈R|一|只有非负的条目。A是自维持的，意味着将RA以一定的速率应用于M上的多重集的反应不会减少A的任何种类的分子的数量。定义2.5M的子集是一个化学（半）组织，如果它是封闭的和（半）自我维持的。这组组织被称为O。为反应网络分配其组织集合的映射称为org。当假设反应网络（M，R）的动力学的质量作用定律时，我们可以给出一个更精确的化学组织概念，称为可行的组织。 让我们用v M，k表示二进制向量函数：|M|→R|R|. 是≥0 ≥0服从速率常数k ∈ R质量作用动力学|R|. 这个动力学定律22P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）19≥0>0个˜˜˜˜˜˜“Feinberg条件”[ 4 ]，即分量v M，k（x）（l，r）（其中（l，r）∈ R）在状态x∈ R中|M|是正的当且仅当l的所有分子都处于状态x否则它是零。这也是真的，并且可以公式化为（M，R）的闭子集，特别是对于组织。定义2.6一个组织O称为k-可行组织，如果存在一个浓度向量x∈R|O|（因此v O，k（x）>0成立），使得S O v O，k（x）≥ 0。 如果一个组织对所有k ∈ R都是k -可行的，|OR|我们称之为可行。3片段在这里，我们概述了片段概念的主要方面[1]，[5]。我们使用κ的一些概念，而不定义它们，例如代理，结合（位点），磷酸化位点，（修饰）位点，模式和模式匹配。 的部分一个模式被称为组件。任何与片段相匹配的模式都被称为子片段。规则可以定义为将模式映射到模式。规则的应用包括绑定删除、代理创建、代理删除和绑定创建四个步骤。我们不描述片段的构造过程，也不描述反应的构造过程，而是仅给出我们稍后需要的一些不同性质，并且提到片段可以从所谓的注释接触图（aCM）直接构造。aCM包括每个代理的站点集合的覆盖现在我们可以公式化下面的四个陈述，它们对[5]和[1]这两个片段，命题VI.4到VI.7都成立。Q1：没有片段与修饰位点上的左侧组分严格重叠。Q2：任何左手侧组件匹配片段，即它是一个亚片段。Q3：任何亚片段的浓度都可以表示为片段浓度的线性组合。Q4：在规则操作下，片段被关闭。对于基于规则的模型（M，R），我们用F表示它的片段集合。当将κ中的表达式表示为图时，可以更自然地使用嵌入而不是匹配的概念。片段F在分子种类m∈M中的可能嵌入的集合由[F，m]表示，即该集合描述了将F匹配到m的所有可能方式。每当我们考虑约化动力学是一组化学常微分方程，因此由一组反应R给出的情况时，我们写为（F，R）。例如，如果aCM中包括的所有覆盖不仅是覆盖，而且实际上是对目标的位点集合的分区，则会发生这种情况然后通过将碎片与规则R匹配来给出R中的反应。将基于规则的模型（M，R）分配给其片段（F，R）的反应网络的映射称为frag。 由于（F，R）是一个反应网络，我们可以计算它的组织. 为了更好的可并行性，我们称（F，R）的组织为f-组织，并将包含它们的集合写成O F。类似于第2节的最后一部分，我们可以定义一个二进制向量函数，P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）1923˜˜˜≥0F，k≥0≥0≥0V：R|F|→R|R|为了碎片，我们去两个地方。它属于质量作用动力学速率常数k∈R|R|.速率k取决于反应R的速率k，并且由构造约化系统的过程给出，参见。附录[5]。片段的抽象由T：R表示|M|→R| F|.它映射分子浓度与片段浓度的比值（因此，如果Tx >0，x >0），并与微分系统交换，此属性也称为的可靠性[1]。4主要结果我们把我们的考虑限制在M和R是有限的情况。我们还假设，所有的覆盖包括在aCM不仅覆盖，但实际上分区的一组网站的代理。在这种情况下，简化模型是一组化学常微分方程，产生这些方程的反应（假设质量作用动力学）通过将R中的规则应用（或匹配）到碎片来给出。如果aCM不满足这个要求，我们可以尝试使用片段上的另外两组反应来计算组织。首先，有一些反应是通过将碎片与规则R匹配而给出的，但是它们产生的常微分方程是不可靠的。那么我们的猜想在某些情况下是正确的，而在另一些情况下是错误的。第5款.但是，由于合理性并不持有的意义的猜想和它的相关性，这些系统是非常有限的。第二，在由化学常微分方程组成的情况下，存在由约化系统如果这些不是由R给出，它们同样具有有限的用途。另一方面，aCM总是可以通过将覆盖类连接在一起来改变。然而，这是以更细粒度的碎片为代价的。到目前为止所定义的对象可以概括在下面的图表中。org（F，R）OFfrag（M，R）Θ？（男、女）orgO其中我们通过它对O∈O的作用来定义Θ：O→OFΘ（O）：={F∈F|f∈O：[F，m]/= f}.我们还注意到，Θ是单调的，即如果O1<$O2，则Θ（O1）<$Θ（O2）。 实际我们还不知道Θ是否映射到OF。这正是我们猜想的陈述。不24P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）19˜˜˜˜˜˜Σ猜想4.1映射Θ被恰当地定义，即 每个组织通过Θ映射到f-组织。引理4.2每个闭集通过Θ映射到一个闭片段集。证据我们固定了一个闭集C<$M，证明了Θ（C）<$F在（F，R）中是闭的. 设反应（εl，rε）∈R，使得满足（εl，rε）εΘ（C ）。我们需要展示prod （nl，rn）θ（C）。 令besupp（fl，rl）={Fl， . ，Fk}和mi∈C <$M使得F i∈ θ（{m i}），其中i = 1，.， K. 存在一个反应（l，r）∈ RC，其中supp（l，r）={m1， . ，m，k}和由Q1和Q2得到的pr，d（l，r），Θ（pr，d（l，r））。由于C是封闭的，h avepr o d（l，r）<$C，因此Θ（pr o d（l，r））<$Θ（C）。Thisshowsprod（l，r）Θ（C）。Q下面的直觉是下一个引理的指导。对于自保持集合G上足够大的多集合，我们可以以适当的速率应用所有可能的反应，使得在应用之后存在相同或更高量的G的每个分子种类。在应用程序之前和之后计算可能的片段嵌入，显然数量没有减少。所以我们想用G的速率来构造Θ（G）反应的速率。在我们的特殊情况下，对于R中的每个反应，R中只有一个反应与之匹配，则Θ（G）的反应速率可以选择为G的反应速率之和。引理4.3每个自保持集合通过Θ映射到片段的自保持集合。证据我们固定了一个自保持集G<$M，证明了Θ（G）<$F在（F，R）中是自保持的.通过我们的假设，反应集RG可以被反 应 集RΘ （G） 划 分。我们认为有一个y（rl，rl）∈RΘ（G）是集合的所有元素和R（l，r1）：={（l1，r1）， . ，（lk，rk）} <$RG·（R1，r2）RΘ（G）∈˜R（Rl，rl）=RG.因为G是自保持的，所以存在一个v∈R|RG|严格的正项使得S G v只有非负项。如果我们设置v（l，r）：=（l，r）∈R（l，r）v（l，r）则SΘ（G）v∈O个非线性项.Q可行组织通过Θ映射到可行f-组织并不明显这里有一个证明这一说法。P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）1925˜>0个k-可行。Q引理4.4如果O是一个k-可行组织，那么Θ（O）是一个k-可行组织。证据 有x∈R|O|其中S 0 v 0，k（x）≥0。 我们也知道Tx > 0并且由于SOvO，k（x）≥ 0，T（SOvO，k（x））≥0.从健全的抽象映射Tw具有0≤T（SOv O，k（x））=SFvF，k∈（Tx）. 因此，Θ（O）5示例我们使用κ-简单的例子在我们的第一个例子中，碎片的数量与分子的数量相同，但组织结构不同。我们定义了我们的示例网络，取两个试剂A和B，分别有一个结合位点a，b和一个磷酸化位点x，y：A（a，x），B（b，y）。规则是A（a），B（b）→A（a！1）B（b！1）;A（xu）ParticipateA（xp）和B（yu）ParticipateB（yp）。这个网络的片段是A（a），A（b），A（a！），A（b！），A（xu），A（xp），B（yu）和B（yp）与反应A（a）+B（b）→A（a！）+ B（b！）; A（xu）ParticipateA（xp）和B（yu）ParticipateB（yp）。在的以下哈苏图表，看到图1，的子集关系组织显示。为了简明扼要，只描述了新出现的物种首先，我们可以看到Lemmata4.2和 4.3是的 的 的 集{B（b），B（yu），B（yp）}， {A（a），A（xu），A（xp）}，{A（a！），A（x u），A（x p），B（b！），B（y u），B（y p）}，{A（a！），A（xu），A（xp），B（b！），B（yu），B（yp），B（b）}和{A（a！），A（xu），A（xp），B（b！），B（yu），B（yp），A（a）}应该是容易被验证的组织。 但还有很多。 综合来看 我们找到了48个如果我们将规则改为A（a），B（b）ParticipateA（a！1）B（b！1）;A（xu）→A（xp）和B（yu）→B（yp），分子的完整集合不再是一个组织，但仍然是一个半组织。从+ B（b！）; A（xu）→A（xp）和B（yu）→B（yp）我们看到片段的全集不是半自保持的。这表明Θ不保持半自维持。聚合严格地说，我们的考虑在这里不适用，因为分子和规则的集合是无限大的。尽管如此，引理4.2和4.3的结论对于聚合也是正确的在该实施例中，片段的数量与分子的数量相比非常小。 我们定义一个简单的聚合如下。 一个特工具有两个结合位点a和b以及一个规则A（a）、A（b）的A→A（a！1）A（b！①的人。这个反应网络的片段是A（a），A（b），A（a！） 和A（b！）与26P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）19反应A（a）+A（b） →A（a！）+A（b！）。 环是一种分子，P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）1927Fig. 1. 组织的Hasse图为简单的例子。 仅显示新出现的物种。未标记的终端节点代表空集。A1（a1！1，b1！k），A2（a2！2，b2！1），.，A k（a k！k，bk！（k−1）），其中k∈N。有机体是所有仅由环组成的集合，因为任何不是环的分子都可以与环反应，因此会违反自维持条件。首先，我们看到引理4.2和4.3的结论说，{A（a！），A（b！）应该是一个f-组织，这是真的。但还有更多，见图。二、其次，更有趣的是，除了上述{A（a！），A（b！）没有其他的例如，不存在AM使得Θ（A）={A（a）}，因为Θ（A）将必须也包括A（b如果我们包含反向规则A（a！1）A（b！1) →A（a），A（b），唯一非平凡的组织是整个集合。 它被映射到{A（a），A（b） ，A（a！），A（b！）}byΘ。f-组织的完整哈斯图3 .第三章。EGF模型我们分析了在[5]中描述的简单EGF模型的组织。这个网络的定义以及（f-）组织的两个Hasse图在附录中提供。28P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）19图二.我们的聚合实例的f-组织的Hasse图。 未标记的终端节点代表空集。因为这里我们在aCM的覆盖类中有重叠，所以我们的证明不适用，但结果仍然成立。这一点在第4节中已经提到。这里的映射Θ是偶内射的但不是满射的。在356个物种中，我们发现了32个组织和66个半组织。附录中的图A.3显示了组织的哈塞图，其图像在Θ下。这组片段由38个元素组成它有56个附录中的图A.4显示了f-组织的哈塞反例如第4节所述，在aCM中存在覆盖类重叠的情况下，存在猜想的反例2，即我们确实有覆盖而不是划分。这会导致过度计数，因为几个片段反应与单个分子反应相匹配。这意味着当应用反应时，会有更多的片段被消耗掉，然后实际的分子被消耗掉。这给出了一种直觉，为什么有组织没有被Θ映射到f-组织。实际2我们把它放在我麻烦的费雷特身上。非常感谢你。P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）1929图三.当包括逆反应时，我们的聚合实例的f-组织的Hasse图。未标记的终端节点代表空集。简化模型的构造恰好考虑了这种过计数现象反例网络的定义以及（f-）组织的两个哈塞图在附录中提供作为一个例子，我们提到，最大的组织被映射到一组片段，这不是一个组织。6结论与展望对于这里考虑的特殊情况下，我们表明，一组片段嵌入（可行的）组织的分子是一个（可行的）组织的片段。所描述的情况大概是唯一有可能在碎片上找到合理的组织概念的情况此外，我们总是可以修改aCM，以便我们的结果保持不变。当然，这是有代价的，因为它增加了碎片的数量。如果（M，R）是相容的，我们知道组织的集合O具有格的结构[3]。 这是否意味着（F，R）也是一致的，并且f30P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）19J因此，组织也有一个网格结构？我们证明了每一种化学组织都对应于一种f-组织，并且可以有几种组织对应于同一种f-组织。然而，我们的例子也表明，有一些f-组织不能被实现为一组分子，例如，有一些不在Θ的图像中。让我们称之为不可实现的，所有其他实现。这立即引发了很多问题，例如。可实现的f-组织的集合是否是一个格，是否存在唯一的最小可实现的f-组织，在什么条件下我们没有任何不可实现的碎片组织在寻找组织时应该特别有帮助。当检查A的一个子集是否是一个组织时，我们有一个新的必要标准，因为Θ（A）需要是一个这一附加标准在实践中是否有帮助，我们需要评估。我们的结果立即激发了通过查看我们的地图Θ的前像来定义组织分类的 我们说O∈ O和OJ∈ O在同一f-类中，如果Θ（O）= Θ（O）。因此，我们得到了我们的组织集合的分区。同一阶级中的组织有什么共同的性质，它们与其他阶级中的组织有什么区别，还有待进一步分析另一个有趣的问题是我们是否可以使用Θ（O）中的片段来进一步描述和结构O引用[1] 达诺斯，五，J. Feret，W.丰塔纳河Harmer和J. Krivine，Abstracting thedifficulty semantic of rule based models：exact and automated model reduction，J. Jouannaud ， editor ， Proceedings of the Twenty-Fifth Annual IEEESymposium on Logic in Computer Science，LICS362-381.[2] Danos ， V. 和 C. Laneve ， Formal molecular biology ， Theoretical ComputerScience325（2004），pp. 69比110[3] Dittrich ， P. and P. di Fenizio ， Chemical organization theory ， Bulletin ofMathematical Biology69（2007），pp. 1199-1231。[4] Feinberg，M.和F. J. M.陈晓，等.开放化学系统的动力学和反应网络的代数结构.化学工程学报，2000，21（1）：117 - 118. 29（1974），pp. 775-787[5] Feret，J.，V. Danos，J. Krivine，R. Harmer和W. Fontana，Internal coarse-graining of molecular systems，Proceedings of the National Academy of Sciencesof the United States of America（PNAS）106（2009），pp.6453-6458[6] 彼得，S.，T. Veloz和P. Dittrich，组织的可行性-化学组织理论的改进及其在P系统中的应用，M。Gheo- rghe，T. Hinze和G. Paun，编辑，第十一届膜计算国际会议论文集（2010年），pp. 369-382.P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）1931A列表A.1反例这里我们列出反例的数据。代理、网站和规则E（a，b）R（a，b，c）0E（a~u）-> E（a~p）1R（a），E（b）-> R（a！1）E（b！第一章2 E（a~p，b！1），R（a！1，b~u）-> E（a~p，b！1）R（a！1，b~p），R（a，b~u，c~u），E（a~u，b）3 E（a~p，b！1），R（a！1，c~u）-> E（a~p，b！1）R（a！1，c~p）物种数量和κ表达：0R（a，b~u，c~u）1E（a~u，b）2E（a~p，b）3R（a！1，b~u，c~u）E（a~u，b！第一章4R（a！1，b~u，c~u）E（a~p，b！第一章5R（a！1，b~u，c~p）E（a~u，b！第一章6R（a！1，b~u，c~p）E（a~p，b！第一章7R（a！1，b~p，c~u）E（a~u，b！第一章8R（a！1，b~p，c~u）E（a~p，b！第一章9R（a！1，b~p，c~p）E（a~u，b！第一章10 R（a！1，b~p，c~p）E（a~p，b！第一章11 R（a，b~u，c~p）12 R（a，b~p，c~u）13 R（a，b~p，c~p）组织数量和设置：0{ }1{ 13}2{ 12}3{ 11}4{ 0}5{ 12 13}6{ 11 13}7{ 11 12}8{ 0 13}9{ 0 12}10 { 0 11}11 { 9 10}12 { 1 2}13 { 11 12 13}14 {0 12 13}15 {0 11 13}16 {0 11 12}17 {9 10 13}18 {9 10 12}19 {9 10 11}20 {0 9 10}21 {0 11 12 13}22 {9 10 12 13}23 {9 10 11 13}24 {9 10 11 12}25 { 0 9 10 13}26 { 0 9 10 12}27 { 0 9 10 11}28 {1 2 9 10}29 {9 10 11 12 13}30 { 0 9 10 12 13}31 { 0 9 10 11 13}32 { 0 9 10 11 12}33 { 0 9 10 11 12 13}32P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）1934 {0 1 2 3 4 5 6 7 8 9 10}P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）1933图A.1.反例的哈斯组织图。 仅显示新出现的物种。 未标记的终端节点代表空集。片段数量和κ表达：0E（a~u，b）1E（a~p，b）2 R（a！1，b~u）E（a~u，b！第一章3R（a，c~u）4R（a，c~p）5R（a，b~u）6R（a，b~p）7 R（a！1，b~p）E（a~u，b！第一章8 R（a！1，b~p）E（a~p，b！第一章9R（a！1，c~p）E（a~u，b！第一章10 R（a！1，c~p）E（a~p，b！第一章11 R（a！1，b~u）E（a~p，b！第一章12 R（a！1，c~u）E（a~u，b！第一章13 R（a！1，c~u）E（a~p，b！第一章F组织数量和设置：第0章1 { 6}2 { 5}3 { 4}4 { 3}5 { 5 6}6 { 4 6}7 { 4 5}34P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）19图A.2.反例的f-组织的哈斯图。未标记的终端节点代表空集。8 { 3 6}9 { 3 5}10 { 3 4}11 { 9 10}12 { 7 8}13 { 0 1}14 { 4 5 6}15 { 3 5 6}16 { 3 4 6}17 { 3 4 5}18 {6 9 10}19 { 6 7 8}20 {5 9 10}21 { 5 7 8}22 {4 9 10}23 { 4 7 8}24 {3 9 10}25 { 3 7 8}26 {3 4 5 6}27 {5 6 9 10}28 {5 6 7 8}29 {4 6 9 10}30 {4 6 7 8}31 {4 5 9 10}32 {4 5 7 8}33 {3 6 9 10}34 {3 6 7 8}35 {3 5 9 10}36 {3 5 7 8}37 {3 4 9 10}38 {3 4 7 8}39 {7 8 9 10}P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）193540 {0 1 9 10}41 {0 1 7 8}42 {4 5 6 9 10}43 {4 5 6 7 8}44 {3 5 6 9 10}45 {3 5 6 7 8}46 {3 4 6 9 10}47 {3 4 6 7 8}48 {3 4 5 9 10}49 {3 4 5 7 8}50 {6 7 8 9 10}51 {5 7 8 9 10}52 {4 7 8 9 10}53 {3 7 8 9 10}54 {3 4 5 6 9 10}55 {3 4 5 6 7 8}56 {5 6 7 8 9 10}57 {4 6 7 8 9 10}58 {4 5 7 8 9 10}59 {3 6 7 8 9 10}60 {3 5 7 8 9 10}61 {3 4 7 8 9 10}62 {0 1 7 8 9 10}63 { 4 5 6 7 8 9 10}64 { 3 5 6 7 8 9 10}65 { 3 4 6 7 8 9 10}66 { 3 4 5 7 8 9 10}67 { 3 4 5 6 7 8 9 10}A.2EGF下面我们来看看EGF的例子。代理、网站和规则E（r）R（l，r，y4，y6）G（a，b）S（y，c）O（d）0E（r），R（l，r）-> E（r！1）R（l！1，r）1E（r！2）R（l！2，r），E（r！1）R（l！1，r）<-> E（r！3）E（r！2）R（l！3，r！1）R（l！2，r！第一章2E（r！3）E（r！2）R（l！3，r！1）R（l！2，r！1，y6~u）-> E（r！3）E（r！2）R（l！3，r！1）R（l！2，r！1，y6~p）3R（y6~p）-> R（y6~u）4E（r！3）E（r！2）R（l！3，r！1）R（l！2，r！1，y4~u）-> E（r！3）E（r！2）R（l！3，r！1）R（l！2，r！1，y4~p）5R（y4~p）-> R（y4~u）6R（y4~p！1，r！）S（y~u，c！1)-> R（y4~p！1，r！）S（y~p，c！第一章7S（y~p，c！） -> S（y~u，c！）8S（y~p，c）-> S（y~u，c）9G（a，b），R（y6~p）→ G（a！1，b）R（y6~p！第一章10 G（a，b！），R（y6~p）→ G（a！1，b）R（y6~p！第一章11 G（a！1，b）R（y6~p！1），O（d）-> G（a！2，b！1）R（y6~p！2）O（d！第一章12 G（a，b），O（d）-> G（a，b！1）O（d！第一章13G（a！1，b）S（y~p！1，c），O（d）<-> G（a！2，b！1）S（y~p！2，c）O（d！第一章14G（a！1，b）S（y~p！1，c！），O（d）<-> G（a！2，b！1）S（y~p！2，c！）O（d！第一章15 R（y ~ 4 ~p），S（y~u，c）→ R（y ~ 4 ~p！1）S（y~u，c！第一章16 R（y4~p！1）S（y~u，c！1)-> R（y ~ 4 ~p），S（y~u，c）17 R（y ~ 4 ~p），S（y~p，c）→ R（y ~ 4 ~p！1）S（y~p，c！第一章18 R（y4~p！1）S（y~p，c！1)-> R（y4~p），S（y4 ~p，c）19 G（a！1，b）S（y~p！1，c），R（y ~ 4 ~p）-> G（a！2，b）S（y~p！2，c！1）R（y ~ 4~p！第一章20 G（a！2，b！1）S（y~p！2，c）O（d！1），R（y ~ 4 ~p）-> G（a！3，b！2）S（y~p！3，c！1）R（y ~ 4 ~p！1）O（d！（二）21 G（a，b），S（y~p，c！1）R（y ~ 4 ~p！1)-> G（a！2，b）S（y~p！2，c！1）R（y ~ 4~p！第一章22 G（a，b），S（y~p，c）→ G（a！1，b）S（y~p！1，c）23G（a，b！），S（y~p，c）<-> G（a！1，b！）S（y~p！1，c）24 G（a，b！2）O（d！2），R（y4~p！1）S（y~p，c！1)-> G（a！3，b！2）O（d！2）R（y~ 4 ~p！1）S（y~p！3，c！第一章36P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）19物种数量和κ表达：0E（r）1E （r！1）R（l！1，r，y4~p，y6~p）2R（l，r，y4~p，y6~p）3G（a，b）P. Kreyssig，P.Dittrich/Electronic Notes in Theoretical Computer Science 272（2011）19374S（c，y~p）5O（d）6E （r！1）E（r！2）R（l！1，r！3，y4~p，y6~p）R（1！2，r！3，y4~p，y6~p）7R（l，r，y4~p，y6~u）8E （r！1）R（l！1，r，y4~p，y6~u）9R（l，r，y4~u，y6~p）10E（r！1）R（l！1，r，y4~u，y6~p）11 S（c，y~u）12G（a！1，b）R（l，r，y4~p，y6~p！第一章13E（r！1）G（a！2，b）R（l！1，r，y4~p，y6~p！（二）14 G（a，b！1）O（d！第一章15R（l，r，y4~p！1，y6~p）S（c！1，y~p）16E（r！1）R（l！1，r，y4~p！2，y6~p）S（c！2，y~p）17 G（a！1，b）S（c，y~p！第一章18E（r！1）E（r！2）G（a！3，b）R（l！2，r！4，y4~p，y6~p！3）R（l！1，r！4，y4~p，y6~p）19E（r！1）E（r！2）R（l！1，r！3，y4~p，y6~p）R（1！2，r！3，y4~u，y6~p）20E（r！1）E（r！2）R（l！2，r！3，y4~p！4，y6~p）R（1！1，r！3，y4~p，y6~p）S（c！4，y~p）21E（r！1）E（r！2）R（l！1，r！3，y4~p，y6~p）R（1！2，r！3，y4~p，y6~u）22E（r！1）E（r！2）G（a！3，b）G（a！4，b）R（l！1，r！5，y4~p，y6~p！3）R（l！2，r！5，y4~p，y6~p！四、23E（r！1）E（r！2）G（a！3，b）R（l！1，r！4，y4~p，y6~p！3）R（l！2，r！4，y4~u，y6~p）24E（r！1）E（r！2）G（a！3，b）R（l！2，r！4，y4~p！5，y6~p）R（1！1，r！4，y4~p，y6~p！3）S（c！5，y~p）25E（r！1）E（r！2）G（a！3，b）R（l！1，r！4，y4~p，y6~p！3）R（l！2，r！4，y4~p，y6~u）26E（r！1）E（r！2）R（l！1，r！3，y4~u，y6~p）R（1！2，r！3，y4~u，y6~p）27E（r！1）E（r！2）R（l！2，r！3，y4~p！4，y6~p）R（1！1，r！3，y4~u，y6~p）S（c！4，y~p）28E（r！1）E（r！2）R（l！2，r！3，y4~p，y6~u）R（1！1，r！3，y4~u，y6~p）29E（r！1）E（r！2）R（l！1，r！3，y4~p！4，y6~p）R（1！2，r！3，y4~p！5，y6~p）S（c！4，y~p）S（c！5，y~p）30E（r！1）E（r！2）R（l！1，r！3，y4~p！4，y6~p）R（1！2，r！3，y4~p，y6~u）S（c！4，y~p）31E（r！1）E（r！2）R（l！1，r！3，y4~p，y6~u）R（1！2，r！3，y4~p，y6~u）32