迭代多线性K-ε-半代数

可在www.sciencedirect.com在线获取理论计算机科学电子笔记276（2011）159-170www.elsevier.com/locate/entcs多重线性迭代K-ε-半代数Z. E'sik1，2部赛格德大学计算机科学系A'rp'ad t'er26720 Szeged，匈牙利摘要我们考虑交换半环K的K-半代数同时也是满足一定线性条件的K-当每一个有限的守护多项式不动点方程组在这样的代数上有唯一解时，我们称之为迭代多线性K-ε-半代数。这类代数的例子包括系数为K的字母表A上的树级数的代数，以及所有有理树级数的代数。本文证明了对许多交换半环K，A上的有理树级数以K为系数构成A上的自由多线性迭代K-S-半代数。关键词：半代数，代数，有理树级数，自由代数，唯一不动点。1引言在迭代代数[1，9，23，20]中，某些定点方程的有限系统有唯一解。在[20]中首次指出迭代代数形成一个拟簇，因此所有的自由迭代代数都存在。显然，这同样适用于任何代数簇或拟代数簇中的迭代代数的子类。然而，在某一类迭代代数中找到自由代数的具体描述通常是一项不平凡的任务。所有迭代代数类中的自由代数可以表示为正则（有限或无限）树的代数，参见。[23]第10段。Salomaa的正则语言公理化[ 21 ]中隐含了正则词语言对自由迭代幂等半环的刻画Salomaa公理化到有理幂级数（或有理加权语言）的扩展1主要由项目TA′MOP-4.2.1/B-09/1/KONV-2010-0005“在赛格德大学创建卓越中心”提供支持，该匈牙利国家科学研究基金会的K 752492电子邮件：ze@inf.u-szeged.hu1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.09.020160Z. Ésik/Electronic Notes in Theoretical Computer Science 276（2011）159所有有限交换半环和交换环）[12]。从这些结果可以看出，在某些迭代半环或迭代半代数类中，自由代数可以表示为有理幂级数代数。(Some沿着这条线的结果在文件中声称[4，24]，但证明是不完整的，如第二篇论文的MR评论中所指出的。）作为具体表示的一个重要结果，人们可以导出相应的方程理论的几个可判定性和不可判定性性质，并使用自动机理论论证来建立方程的有效性。例如，可以得出[23，20]的迭代代数的方程理论在多项式时间内是可判定的，而迭代幂等半环的方程理论是PSPACE-完备的，参见[23，20]。[22 ]第20段。本文的目的是将文[12]中的一些结果推广到“itera-定的多线性K-代数主要结果表明，当K是适当的时，自由迭代多线性K-R-代数可以用有理树级数来描述[8]。这个结果适用于自然数的半环N，所有有限交换半环，所有交换环，所有诺特交换半环，事实上也适用于所有交换半环K，使得K的每个有限生成子半环都包含在诺特子半环中。唯一不动点规则是计算机科学中几个完整公理化结果的基础。除了自动机和语言之外，它还经常用于并发，例如参见[17，18，5]。我们的自由度结果产生了一个这样的完整性结果的有理树系列（正规加权树语言）[8，11]。2迭代多线性代数一个半环S =（S，+，·，0，1）由一个交换幺半群（S，+，0）和一个幺半群（S，·，1）组成，使得乘积分布在所有有限和上，包括空和，使得对所有x ∈ S，x·0 = 0 = 0·x。半环的例子包括所有环，自然数的半环N和集合{0，1}上的布尔半环B，其和运算是析取，其积运算是合取。交换半环是乘积是交换的半环。设K=（K，+，·，0，1）是一个交换半环，K是一个秩集.一个多线性K-B-代数B既是一个具有运算σB：Bn→B的B-代数，对所有的σ∈Bn，n≥0，又是一个具有左K-作用K×B→B的K-半模（B，+，0），其中x，y，z∈B，k，KJ∈K：（一） （x+y）+z=x+（y+z）(2)x+y=y+x(3)x+0 =x(4)（k+kJ）x=kx+kJx(5)0x =0Z. Ésik/Electronic Notes in Theoretical Computer Science 276（2011）159161Σi=1i=1(6)k（x+y）=kx+ky(7)k0=0(8)（kkJ）x=k（kJx）(9)1x =x此外，对于所有σ ∈ n，i∈ [n] ={1，...，n}，n > 0且k∈ K：(10)σ（x1，...，xi+ yi，.，xn）= σ（x1，...， xi，.， xn）+ σ（x1，...， 是的， xn）（11）σ（x1，.， kxi，.， xn）= kσ（x1，.， xn）。多线性K-代数的态射既是K-代数态射又是K-半模态射。下面我们经常用σ来表示代数B的运算σB。接下来，我们将考虑具有两种变量的不动点方程组，即出现在方程左侧和可能出现在右侧的变量，以及只出现在方程右侧的变量。我们将后者称为参数。集合X ={x1，...，xn}的变量和参数的集合A由上下文无关文法给出t：：= xi|一|0 |t + t |KT |σ（t，.， t）的范围内其中k在半环K上的范围，xi是变量，a是参数。当σ∈Σ0，我们用字母σ来标识项σ（）。多线性K-代数B中的参数集合A的解释将B的元素分配给A中的每个参数a，通常也表示为a。 给定一个多线性代数B连同参数A的一个解释作为B的元素，{x1，.，xn}在参数A中导出一个多项式函数tB：Bn→ B，以通常的方式定义。关于多线性K-S-代数的公理（1）在X中的变量和参数A上的t等价于以下形式的项：Mi=1 kiti，其中每个ki是K的非零元素，每个ti是不包含+、0和K-作用的任何出现，即，每一个ti都是一个n项。（当m= 0，则该项为0。）我们不妨假设ti都是不同的，其中在这种情况下，项kiti直到被加数的排列都是唯一的。下面我们通常会确定在多线性公理下等价的项，K-代数定义2.1假设X是一组变量，A是一组参数。我们称参数A中的X上的项t为适当的（或保护的），如果它是0，或A中的字母a，或形式为σ（t1，...，tn），σ ∈ n，n≥ 0，其中t1，.，tn是X上参数A中的任一项，或一个形式为kt或t1 + t2的项，其中t，t1，t2是真项，k∈K.因为对于任何项t，项0t可以与0等同，我们也可以允许形式为0t的真项，其中t是任何项。当t是一个真项时，它等价于一个项mkiti，其中每个ki是一个162Z. Ésik/Electronic Notes in Theoretical Computer Science 276（2011）159我Σ⎩nK的非零元素，并且每个ti都是X中不是单个变量的一项。定义2.2假设B是一个多线性K-代数。 我们说B是一个迭代多线性K-代数，如果对每个序列t1，…，tn是集合X ={x1，.，xn}的变量和一组参数A解释为B的元素，B是真不动点方程的有限系统x1=t1(12).xn=tn有唯一解迭代多线性K-代数的态射就是多线性K-代数的态射。因此，如果B是一个迭代多线性K-代数，则对于任何不动点方程组（12），存在唯一的n元组（b1，...，bn）∈Bn，其中bi= tB（b1，...，bn）对于所有i.当E表示系统（12）时，我们表示唯一解（b1，...，bn）通过|E|B.我们用一个例子来结束这一节假设A是一个集合。A上的一棵树是由上下文无关文法从A中的字母生成的一个词t：：= a|σ（t，.， t）的范围内其中a ∈ A，σ ∈ n，n ≥ 0. 设T∈（A）表示A上所有树的集合.则T∈（A）自然是A上的自由π-代数，π-代数。A上的系数在半环K中的树级数[11]是函数s：T∈（A）→K，有时记为形式和t∈T<$（A）（s，t）t，其中（s，t）=s（t）∈K.让KT（A）表示所有级数的集合我们可以通过逐点地装备KT（A），求和运算和逐点作用，使它成为一个K-半模，其中性元为常零级数，记为0。对于每个σ∈n，n≥ 0，对于级数s1，…， sn，让我们定义s = σ（s1，...， sn）由巴恩（s，t）=（si，ti）如果t = σ（ti，.， tn）0否则。我们通过将t映射到1，将所有其他树映射到0的序列来标识每个树t当K是可交换的时，KT（A）成为一个多线性K-代数，并且实际上是一个迭代的多线性K-代数，参见例如，[7]的文件。上述结构可以推广。称一个B-代数为B有限可分解的，如果对任意σ∈Bn，每个b∈B只能有有限个不同的形式表示为b = σ（b1，...，bn），其中b1，...，bn∈B。 则KB，所有级数B→K的集合可以配备点态和K-作用，（σ（s1，.， sn），b）=n（si，bi）b = σ（b1，...，bn）i=1对所有σ∈ <$n，n≥0.当K是交换的时，K∈B∈ K是一个多重线性K-半代数。然而，KB不必是迭代多线性K-半代数。i=1Z. Ésik/Electronic Notes in Theoretical Computer Science 276（2011）159163i=1我我称一个n-代数B是饱和的，如果存在函数n：B→N使得对所有σ∈ n和b1，.，bn，n（σB（b1，...，bn））> max {n（bi）：i∈ [n]}.显然，T（A）被通常的高度函数饱和。命题2.3对任意交换半环K和饱和有限可分解K-代数B，K∈B∈ A是一个迭代多线性K-代数.证明大纲。 设E是环X ={x1，...，x2，...，x3，...，x4，...，x5，...，x6，...，x8，...，x9，...，x10，..，x10， xn}，如在（12）中那样。进一步假设每个参数a∈A被解释为B的一个元素。我们可以把每个方程的右边ti写为tJi+tJiJ，其中tJiJ项不包含任何变量。每一项tJiJ的值都是K B中的一个级数ri。假设（s1，.，sn）是E在K B上的解。则对于每个b∈B，每个（si，b）是（ri，b）与K中的一个元素的和，该元素完全由（sj，bJ）确定，其中<$ （bJ）<$（b）。<因此，解决方案是独一无二的。此外，由于每个（si，b）仅依赖于（ri，b）和具有<$（bJ）<<$（b）的值（s j，b j），因此我们可以通过对<$（b）的归纳来定义（si，b），使得（s1，...， Sn）成为一种解决方案。Q当A是一个集合时，设RelA表示A上的二元关系的半环，其和运算是并，其积运算是关系的合成。常数0和1是A上的空关系和恒等关系。因为RelA是幂等的，我们可以把它看作是一个B-π-半代数，其中π仅由乘法符号·和常数1组成。然而，它不是迭代的，因为不动点方程可能有许多解。3一些结构设K表示交换半环。在这一节中，我们定义表示迭代K -代数的“有理”元素的描述扁平描述对应于加权树自动机。然后给出了几种关于刻划的（标准）构造，并从这些构造中得到了迭代K-代数的有理元素本身构成迭代K-代数的事实.定义3.1假设D是变量X ={x1，...，x2，...，xn}和参数A.此外，假设v =（v1，...，vn）∈Kn.然后我们称对（v，D）为在参数A中的Xn上的描述。一个描述（v，D）被称为描述t，如果D的每个方程的右边是（等价于）形式为kt的子项的有限和，其中t的形式为σ（xj1，.，xjm）或ka，对k∈K，k/= 0，σ∈φm，m≥ 0，j1，...，jm∈[n]和a∈A. (We通常还假设，如果kt和ktJ 都 是被加数，则t i = tJ）。当B是一个迭代多线性K-代数，且A中的参数解释为B的元素时，（v，D）在B上的行为是|（v，D）|B = nvi|D|B∈B，其中|D|B表示的第i个分量|D|B，对于所有i∈ [n]。 两个描述在B上等价，如果在每个参数的解释下，它们在B上具有相同的行为。此外，如果两个描述在所有迭代多线性K-代数上等价，则它们是等价的164Z. Ésik/Electronic Notes in Theoretical Computer Science 276（2011）159z=Bi=1B命题3.2对于每一个摹状词（v，D），都有一个等价的摹状词（w，E），使得w的第一个分量为1，所有其他分量为0。当（v，D）是可解的，那么（w，D）也是可解的。证据当D是X ={x1，...， xn}在参数A中 ，如果v =（k1，...，第一 个 方程是 ：ni=1 kiti，其中t1，.， tn分别表示方程的右侧对于x1，...，xn和z是一个新的变量。 E的其他方程是D的方程。当（v，D）是可拓的时，利用K -半模的公理，（w，E）可化为一个等价的可拓刻划.Q在X ={x1，...，xn}可以被看作是加权树自动机，其状态集是{q1，.，qn}，其中qi对应于xi，对所有i ∈ [n]，它有一个转移（qi1，.，qim）→qi标记为σ∈ Σ m的权重k i <$kσ（xi1，.，xim）是D的第i个等式的右侧的被加数。当ka是该项的被加数时，则qi是a-初始，重量K 最后，每个状态qi使得viv的组成部分。0是最终的，权重为vi，第i个让我们将每个参数a∈A解释为KT（A）中与a相关联的级数，它将a映射到1，将所有其他树映射到0。那么K上的（v，D）的行为就是相应的加权树自动机的通常行为[8]的一项建议。在本节的其余部分，我们将提供一些描述的结构，这些结构将在后续部分中使用。 假设（v，D）和（w，E）是不相交的变量集X ={x1，.，xm}，Y ={y1，.，yn}中。然后我们定义（v，D）+（w，E）为在参数A中对X∈Y的描述（（v，w），（D，E））。此外，对于每个k∈K，我们定义k（v，D）为X上的描述（v，D）。命题3.3对于任何迭代多线性K-代数B，其中A中的每个参数都解释为B的元素，我们有|(v, D)+ (w, E)|为|（v，D）|+的|（w，E）||k(v, D)|= k|（v，D）|如果（v，D）和（w，E）是可解的，那么（v，D）+（w，E）和k（v，D）也是可解的。假设σ ∈ n，令（v1，D1），. （vn，Dn）是两两不相交（有序）变量集X1，.，在参数A.在不失一般性的情况下，我们可以假设每个vi的第一个分量是1，每个vi的其他分量是0。然后我们令σ（D1，.，Dn）表示第一个分量为z = σ（x11，...，xn1），其中每个xi1是X i的第一个变量，z是一个新变量。剩下的方程是Di，i = 1，.， n.最后，我们定义σ（（v1，D1），.， （vn，Dn））到是描述（v，σ（D1，.，Dn））在nXi上，其中，v的第一个分量（对应于变量z）是1，它的其他分量BBBZ. Ésik/Electronic Notes in Theoretical Computer Science 276（2011）159165i=1BBBB都是0。注意，如果每个（vi，Di）是σ t，则σ（（v1，D1），.，（vn，Dn））。特别地，当σ∈Σ0时，则对应的描述是（vσ，Dσ），其中Dσ由单个方程z=σ组成，并且vσ的唯一分量是1。以类似的方式，我们可以将描述（在空变量集上）（v0，D0）与0相关联，并将描述（va，Da）与每个a∈A相关联。命题3.4在任何把参数A解释为B的元素的迭代多线性K-代数B中，B|σ ((v1, D1),..., （vn，Dn））|=σ（|（v1，D1）|，...，|(vn, Dn)|） 的方式|(v0, D0)| = 零|(va, Da)| =a定义3.5假设B是一个迭代多线性K-代数，其参数A被解释为B的元素。然后我们让RatB（A）表示所有b∈B的集合，这些b是参数A在B上的某些描述关于参数的给定解释特别地，当B是KT（A），并且每个参数都被解释为相应的级数时，则我们用KratT（A）来表示RatB（A）。在第五节中，我们将刻划KratT（A）为A上的自由迭代K--半代数，对各种交换半环K。命题3.6假设B是一个迭代多线性K-代数，其参数A被解释为B的元素。 则对于每个b∈ RatB（A），在参数A中存在一个严格的描述，其在给定的解释下对B的行为是b.证据 假设b =|（v，D）|把每一项写在右边，D的方程，形式为mkiti，其中项ti不包含任何出现项0或K-作用的，并且对于所有i，ki/= 0，并且没有ti是单个变量。 如果某个ti是 形式为σ（s1，...，sn）其中某个si不是一个变量，那么我们用一个新的变量z来代替si，并引入方程z = si。通过继续这个过程，我们最终得到了一个等效的Wavelat描述，其中对应于新引入的变量都是0。例如，当初始描述为（（k1，k2），（x1=kσ（σ（a，x1），x2）+KJσ（x1，x2），x2=σ（b，x1）），则等价的描述为（（k1，k2，0， 0），E）其中E是以下方程组：x1=kσ（x3，x2）+kJσ（x1，x2）x2=σ（x4，x1）x3=σ（x5，x1）x4=bB166Z. Ésik/Electronic Notes in Theoretical Computer Science 276（2011）159.1na1nai=1我我我x5 = a。Q定理3.7对每个把参数A解释为B的元素的迭代多线性K-代数B，Rat B（A）是一个迭代多线性K-代数. 它是B的包含A的最小迭代多线性K-S-子代数。证据在不失一般性的情况下，我们可以假设A→B和A中的每个参数都是由其自身解释的RatB（A）是一个多线性K-代数的事实从命题3.3和3.4中可以清楚地看出。我们证明了它是一个迭代的多线性K-代数。 出于这个原因，假设AJ是一组参数，其解释为Rat B（A）的元素，并且（v，D）是对X ={x1，...，xn}中的参数AJ，其对B的行为是b，比方说。在不失一般性的情况下，我们可以假设每个参数a∈AJ实际上在B中并且被自身解释对于每个a∈AJ存在对某个集合Xa={Xa，.，xa}个变量，参数A，|（va，Da）|B = a。 对于每个a ∈ AJ，令va=（va，.， va）和设DJ是从D通过替换以下的每次出现而获得的方程组：a参数a∈AJ， vata，其中对于每个i，ta表示第i个方程Da. 最后，设1，...，ak是D中出现的所有参数，并考虑描述（（v，0，...， 0），（DJ，Dal，...， Dak））。这个描述（在参数A中）对B的行为显然是b。Rat B（A）是B的包含A中参数的解释的最小多线性K-子代数的事实通过定义是清楚的。Q4模拟在本节中，在和[6，10，14]之后，我们介绍了描述之间的模拟，并表明可以通过一系列模拟连接的描述是等效的设K表示交换半环。设D和E是X={x1，…，xm}且Y={y1，...，yn}中。设xi=si，yj=tj，i∈[m]，j∈[n]分别表示D和E当M∈Km×n时，我们定义DM为将D方程右侧的每个变量xi的每次出现替换为Mi1y1+.得到的方程组。+Minyn：x1 = s1（M11y1 +. + M1 nyn，...， Mm1y1 +. +Mmnyn）.xm= sm（M11y1 +. + M1 nyn，...，Mm1y1 +. +Mmnyn）Z. Ésik/Electronic Notes in Theoretical Computer Science 276（2011）159167此外，我们让ME表示方程组：x1 = M11t1 +. +M1ntn.xm= Mm1t1+. + Mmntn定义4.1假设（v，D）和（w，E）是对 X={x1，.，xm} 和Y = {y1，.，yn} 在参数A的集合中。 仿真（v，D）→（w，E）由矩阵M∈Km×n给出，使得vM=w，且DM的每个方程的右侧与ME的相应方程的右侧关于多线性K-M-代数的公理在文献[2，3]中，用模拟连接的普通加权（字）自动机称为共轭自动机定理4.2假设（v，D） 和（w，E） 是对X的描述={x1，.，xm}且Y ={y1，...，yn}，如上所述。 此外，假设M是模拟（v，D）→（w，E）。 故（v，D）和（w，E）是等价的。证据设B是一个迭代多线性K-代数，A中的每个参数都被解释为B的一个元素，并且设（c1，…，cn）是E在B上的唯一解。 定义b1，.，bm乘bi= Mi1c1 +.+Mincn对于每个i∈[m]。然后sB（b1，.，bn）= sB（M11c1 +. + M1 ncn，.，Mm1c1 +. +Mmncn）我我= Mi1tB（c1，.， cn）+. + MintB（c1，.， cn）1N= Mi1c1 +. +Mincn=bi，对于所有i∈[m]。 因此（b1，.，bm）∈Bm是B上的解D，表明|B = M|E|B .|B . 利用这个，|（v，D）|B = v|D|B = vM|E|B = w|E|B.Q定义4.3我们说交换半环K是真的，如果对于X和Y上的所有参数A中的k（v，D）和（w，E），如果当每个参数a被解释为相应的树序列时，（v，D）和（w，E）在K上等价，则存在一个模拟序列连接它们，即， 存在序列（v1，D1），.，（vk，Dk）的参数A和模拟Mi中的描述：（vi，Di）→（vi+1，Di+1）或（vi+1，Di+1）→（vi，Di），i=1，.，k−1使得（v1，D1）=（v，D）且（vk，Dk）=（w，E）。在[14]中，证明了所有交换环都是真环。更一般地说，我们称一个（交换）半环为诺特环，如果对每个有限生成的K-半模M，M的每个子半模都是有限生成的。[14]证明了如果K是Noether的，或者K的每个有限生成子半环都包含在一个Noether子半环中，则K是真的。特别地，每个局部有限的3（交换）半环，从而每个有界分配格都是真的。那里3一个半环是局部有限的，如果它的有限生成子半环是有限的。168Z. Ésik/Electronic Notes in Theoretical Computer Science 276（2011）159大鼠存在不是诺特的真半环，例如半环N，参见。[3、14]。一个不适当的半环的例子是“热带半环”，参见。[13 ]第10段。推论4.4假设K是真的。 则对于X和Y上的任意一个参数A上的（v，D）和（w，E），如果当每个参数a被解释为对应于a的树序列时，（v，D）和（w，E）在K上等价，则（v，D）和（w，E）是等价的。5游离度在本节中，我们证明了我们的主要结果：定理5.1设K是真交换半环。对于每个集合，A，KratT（A）是A上的自由迭代多线性K--半代数.证据我们已经知道（cf。定理3.7）证明了KratT（A）是一个迭代的多线性K--代数。设η表示映射（解释），它为每个a∈A分配相应的级数，也记为a，它将a映射到1，将T（A）中的所有其他树映射到0。Krat中的每一个系列都是在这种解释下参数A由于多线性K-R-代数的态射保持真多项式不动点方程的唯一解，因此对于任何迭代多线性K-R-代数B和函数h：A→B，至多有一个态射h：KratT（A）→B扩张h。实际上，当S =|（v，D）|K<$T<$（A）<$对于参数A中的描述（v，D），在解释η下，我们被迫将h（s）定义为|（v，D）|B关于将每个参数a映射到h（a）的解释，在其余的证明中，我们证明了扩张的存在。令h：A→B。当s∈KratT（A）时，参数A中存在一个描述（v，D），其在KratT（A）上关于解释η的行为是级数s。我们定义h（s）：=|（v，D）|B，同一描述在B上关于解释h的行为。由于K是适当的，如果（w，E）是另一个关于η的行为在K上的另一个描述，那么根据推论4.4，|（v，D）|B =|（w，E）|B.因此，h（s）的定义并不依赖于对描述（v，D）的选择，描述（v，D）在Krat上关于η的行为是s。根据这些事实和上面给出的构造，现在可以得出h是一个态射。我们只证明了h保持π-运算。为此，设σ ∈ n，其中n≥ 0，且设s1，.，sn∈KratT（A），s = σ（s1，...，sn）。对于每个i，设（vi，Di）是一个关于η在Krat上的行为为si的随机描述.设（v，D）= σ（（v1，D1），.，（vn，Dn）），所以（v，D）也是可解的。则（v，D）在Krat上的行为是s.根据定义，h（si）=|（vi，Di）|B，对于所有i∈ [n]，且h（s）=|（v，D）|B（关于解释H）。但根据3.4号提案，|（v，D）|B = σB（|（v1，D1）|B，... |B），使得h（s）= σ B（h（s 1），...，|B ), so that h(s) = σB(h(s1),..., h（sn））。QZ. Ésik/Electronic Notes in Theoretical Computer Science 276（2011）159169∗定理5.1适用于N和所有交换半环K，使得K的每个有限生成子半环包含在诺特子半环中。特别地，定理5.1适用于所有交换环和包括B在内的所有局部有限交换半环。当K是B时，定理5.1通过唯一不动点规则[15]暗示了正则词树语言的公理化，并且当另外的K由一元字母组成并且A是单点集时，则定理5.1通过唯一不动点规则暗示了正则词语言的Salomaa定理5.1经过一些明显的修改，可以推广到交换迭代多线性K-ε-代数，σ（x1，...，xn）= σ（x1 π，.， xnπ）对于所有σ∈n和所有排列π：[n]→[n]。我们需要用“无序”的树来代替树6结论我们可以把每个集合都看作是一个排序集合，所有字母的秩都是1。因此，我们可以用树t∈T（{a}）来识别词u∈T，其中a是一个固定的参数。在这种识别下，正则树语言对应于正则树语言T（{a}），反之亦然。萨洛马的正则词语言公理化可以表述为这样的断言：对于任何（有限）集合，B rat T（{ a }）由所有迭代B--代数类中的字母a自由生成。在我们的主要贡献定理5.1中，我们把Salomaa的刻划推广到了K-代数K rat T（A），其中K是真交换半环，T是任意秩集，A是任意自由生成元集。真交换半环包括N，所有局部有限交换半环和所有交换环。引用[1] J. Ad'amek，S. Milius和J. Verebil，Iterati v e algebrasatwock. 数学结构计算。 Sci. ，16（2006），1085-1131中所述。[2] M.- P. B'eal，S. 我很好，J。 Sa kar ovit ch，关于Z-自动机的等价性。In：Proc. ICALP2005，LNCS3580，Springer，2005，397-409。[3] M.- P. B'eal，S. Lo mbardy和J. Weighted自动机和函数变换器的共轭性和等价性。In ：Proc.CSR2006，LNCS 3967，Springer，2006，58-69。[4] D. 本森和我。Guessarian，Iterative and Recursive Matrix Theories. J. Algebra，86（1984），302-314.[5] J. A. Bergstra和J. W. Klop，一个完整的推理系统，为正规过程与沉默的举动。见：Proceedings，LogicColloquium 1886，（F。R.德雷克和J. K。Truss编），North-Holland，Amsterdam，1988，21[6] S. L. Blo om和Z. E'sik，IterationTheories，Springer，1993.[7] S. L. Blo om 和Z. E'sik，一个扩展定理及其在形式树 级数 中的应 用， J。 Automata ，Languages andCombinatorics，8（2003），145-185.[8] M. Droste，W.Kuich，H.Vogler（eds.），Handbook of Weighted Automata，Springer，2009.170Z. Ésik/Electronic Notes in Theoretical Computer Science 276（2011）159[9] C. C. Elgot，Monadic Computation and Iterative Algebra Theories. In：Logic Colloquium[10] Z. E'sik和W. 崔昌昌，正则集的方程理论的一个推广，《词、半群和转换》，M。伊藤湾Paun，ShengYu，eds.，世界科学，2001年，99[11] Z. E'sik和W. Kui ch，F正规树系，J. Automata，LanguagesandCombinatorics，8（2003），219- 285.[12] Z. E'sik和W. Kui ch，Free迭代与迭代K-半代数，Alg. 普适性，以适应耳朵。[13] Z. E'sik和A. 马莱蒂，模拟vs. 等价。在：P roc. 第六届国际 Conf. 计算机科学基础，FCS 2010，（内华达州拉斯维加斯），CSREA出版社，119-122。[14] Z. E'sik和A. Maletti，树自动机的模拟。In：Proc. 第15届 国际 Conf. 自 动 机 的 实现和应用，温尼伯，加拿大，2010年，LNCS，Springer，出现。[15] T. Ito和S. Ando，超正则表达式的完备公理系统。In：Information processing 74（IFIP Congress，Stockholm），North-Holland，Amsterdam，1974，661[16] D. Krob， RationalExpressions over a Ring 。 在 ： 主 题 不变 理 论（ 巴 黎， 1989/1990 ） ， 讲 义数 学 ，1478，Springer，Berlin，1991，215[17] R. Milner，A complete inference system for a class of regular behaviors. J.计算机系统科学，28（1984），439[18] R. Milner，A complete axiomatisation for observational congruence of finite-state behaviors. 告知。的Comput。，81（1989），227[19] M. Morisaki和K. Sakai，A complete axiom system for rational sets with multiplicity。理论计算。Sci. ，11（1980），79[20] E. Nelson，Iterative Algebras.理论上Comput. Sci. ，25（1983），67[21] A. Salomaa，正则事件代数的两个完备公理系统。J. Assoc. Comput.马赫，13（1966），158[22] L. J. Stockmeyer和A. R. Meyer，需要指数时间的Word问题。在：73年斯托克会议上 ACM，1973，1[23] J. Tiuryn，独特的固定点与最少固定点。理论上Comput. Sci. ，12（1980），不。3，229[24] W. Wechler，Iterative Nondeterministic Algebras。 Studia Automat. ，13（1989），35