可在www.sciencedirect.com在线获取理论计算机科学电子笔记348（2020）43-60www.elsevier.com/locate/entcsFuzzyAutomata1中同步性的引入莱昂德罗·戈麦斯2INESC TEC葡萄牙米尼奥布拉加大学亚历山大马德拉3CIDMA葡萄牙阿威罗大学Luis Soares Barbosa4INESC TEC葡萄牙米尼奥布拉加大学联合国大学GuimarMogaes，葡萄牙摘要本文介绍了一种自动机和相关的语言，经常出现在模拟自然现象，其中的相似性和相似性都被视为第一类公民。这需要为转换分配模糊语义，以及同步产品的精确概念，以强制动作的同时发生。自动机和语言之间的预期关系被重新审视在此设置，特别是它表明，任何子集的模糊同步语言与适当的签名形成一个同步Kleene代数。保留字：模糊自动机，模糊语言，同步语言。1这项工作由ERDF-欧洲区域发展基金通过竞争力和国际化运营计划- COMPETE 2020计划提供资金，并由葡萄牙资助机构F C T -Funda c a op a r a C i e a T ecnologia的国家基金提供资金，资金来源于POCI-01-0145-FEDER-030947和UID/MAT/04106/2019。第二作者在8月29日第57/2016号法令第23条第4、5和6条所预见的框架合同范围内得到支持，该范围经7月19日葡萄牙法律57/2017号修改。本文也是SmartEGOV项目的成果：利用EGOV进行智能治理（基础，方法，工具）NORTE-01-0145- FEDER-000037，由葡萄牙北部区域运营计划（NORTE 2020）支持，葡萄牙2020年伙伴关系协议，通过欧洲区域发展基金（EFDR）。它得到了PT-FLAD智能城市智能治理主席2电子邮件：leandro.r. inesctec.pt3电子邮件：madeira@ua.pt4电子邮件：lsb@di.uminho.pthttps://doi.org/10.1016/j.entcs.2020.02.0041571-0661/© 2020作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。44L. Gomes等人/理论计算机科学电子笔记348（2020）431介绍自动机的概念[7]作为离散空间上计算过程的事实上的数学抽象，正在不断地被重新审视，以捕捉在最不同的上下文中的不同类型的计算行为，无论是在程序中预先描述的还是在自然界中发现的。早在1997年，罗宾·米尔纳（Robin Milner）就强调，从一个如何做某事的处方用随着时间的推移，不同种类的自动机被提出来，产生（或识别，取决于视角）这些行为（或表达它们的语言）[2，3，21]。在这种背景下，Kleene代数被引入[8]。作为一种代数结构来公理化地捕获正则表达式的基本属性。本文重点关注一种特殊的自动机和语言，它们通常出现在自然现象的建模中，其中两个额外的成分不容忽视。第一个是庄严。例如，在生物网络中另一个是并行性，即某些事件（例如化学反应中某些试剂的流动）需要同时发生，而不是像通常在并行交错模型中考虑的那样，以非确定性的交替发生。第一个成分--模糊性--通过模糊有限状态自动机（FFA）的概念形式化，这是六十年代引入的一种结构[23]，为几个计算系统固有的模糊性提供了形式语义。这种想法的变体，例如将fuzzy结合到状态或转换中，或两者，在文献中有很好的记载[3，10，12]。在任何情况下，模糊语言[9，1]只能在一定的隶属度下被FFA识别应用程序是横向到几个领域[11，16，17，24]。概率自动机[19]是处理不确定性的另一种方法，它将后者的解释固定为概率，总是强制产生一个结果（正如输出概率总和总是为1的要求所表示的那样）。这是不是在本文中采用的模糊框架的情况下。反过来，我们的第二个要素，即同步性，在米尔纳所谓的“CCS的同步版本”中得到了适当的形式化同样的同步进化思想也出现在C.Piscariu关于同步Kleene代数（SKA）[18]. Kleene代数是幂等的，因此是偏序的，半环被赋予一个闭包算子。SKA的模型，以及其L. Gomes等人/理论计算机科学电子笔记348（2020）4345带有测试的变体（SKAT），是以同步字符串和接受同步字符串的有限自动机的集合给出的。例如，这些结构在道义逻辑的变体中找到了应用，以形式化合同语言[20，22]，并且Hoare逻辑用于推理具有共享变量的并行同步程序[18]。开始图1.一、交错两个自动机代表确定性的流水线。本文将这两种成分结合起来我们所设想的那种系统如图1所示1.一、 假设两个自动机表示两个试剂c和m进入溶液的流动。图1的方案将它们的交织表示为两个替代的顺序合成。然而，我们的目标有不同的重点。首先，我们打算记录基本步骤是“不确定的”，在这个意义上，每个单独的流程可能会出现故障或中断。的过渡因此，自动机中的每个事件都被标记了一个第二，它们的组合确保两个连续流（动作）同时发生，将它们的“确定性”程度组合这些功能在模糊同步自动机中表达，本文提出将其添加到上述有限状态自动机的广泛家族为了形式化这样的行为，本文介绍了一个同步产品之间的模糊转换自动机的一个变种的参考文献[12]的精神，其中，根据应用场景，“模糊性”可以在一个任意的，离散或连续，域建模。这是捕获的一个完整的海廷代数作为一个参数引入模型。参考文献[18]中的同步集的概念被推广到模糊同步语言中，并适当地定义了它们上的一些算子。一个地图，解释的条款SKA模糊同步语言。 然后证明SKA的条款可以用来生成H-NFA，模糊同步语言，构成其解释。从H-NFA中获得正则表达式是通过状态消除进行的，就像经典情况一样。[6]的文件。该过程导致H-NFA具有从初始到最终状态的单一跃迁，标记为SKA的作用α，使得其解释为H-NFA认可语言本文件的结构如下。第2节概括了后面需要的一些基本概念。第3节介绍了模糊同步语言，并定义了一些合适的算子。第4节介绍了一种构造y0My1CCy2My346L. Gomes等人/理论计算机科学电子笔记348（2020）43××两个具有模糊转换的不确定自动机的同步乘积。证明了由任意模糊同步语言集合和前面定义的签名构成的代数构成一个SKA。最后，第五节总结并列举了未来研究的一些主题2预赛定义2.1（Kleene代数）Kleene代数（K，+，·，K，0，1）是一个幂等半环，其额外的一元算子满足图2中的公理（1）-（13）。偏序≤定义为α≤β惠α + β = β。运算符+、·和通常分别被理解为非确定性选择、序列和迭代。操作0和1表示失败和跳过，重新启动。Kleene代数的著名例子是集合X上的二元关系代数、集合X上的所有语言的集合和（min，+）代数，也被称为热带代数。用一个操作来捕捉动作5的同步执行扩展原始定义，导致同步Kleene代数的概念[18]。定义2.2（同步Kleene代数）同步Kleene代数（SKA）是一个元组S=（A，+，·，×，，0，1，AB）其中AB是基本动作的有限离散集合，A是（可能无限）组成的行动，满足图中的公理。二、函数集A和AB由AB <$A×B<$A构成，其中AB是基本作用集，A×B是它在×下的闭包.我们表示由TSKA的长期代数SKA，所产生的语法：α：：= ab|0|1|α + α|α·α|α ×α|α∗其中ab∈AB。 按照通常的做法，我们写abbb，而不是ab·bb，因为ab，bb∈AB。A ×B的元素称为×-作用（例如， a，a×b∈A×B但a+b，a×b+c，0，1∈/A×B）。定义2.3（完备海廷代数）完备海廷代数（CHA）是一个元组H=（H，+，;，0，1，→）（1）（9）（1）（2）（3）（4）（5）（6）（7）（8）（9）（ 2，替换为;此外，下面的公理：[5]在[18]之后，符号代表同步乘积;任何可能与笛卡尔乘积使用的相同符号混淆的情况都可以通过上下文来消除歧义L. Gomes等人/理论计算机科学电子笔记348（2020）4347+（β+γ）=（α+β）+γ（一）α+β=β+α（二）α+α=α（三）α+0=0+α=α（四）α·（β·γ）=（α·β）·γα·1=1·α=α（五）（六）α·（β+γ）=（α·β）+（α·γ）（七）（α+β）·γ=（α·γ）+（β·γ）α·0= 0·α=01+（α·α）=α（八）（九）（十）1+（α·α）=α（十一）β+α·γ≤γαβ·β≤γ（十二）β+γ·α≤γβ·α≤γα×（β×γ）=（α×β）×γ α×β=β×α（十三）（十四）（十五）α×1=1×α=α（十六）α×0= 0×α= 0ab×ab=abα×（β+γ）=（α×β）+（α×γ）ab∈ AB（十七）（十八）（十九）（α+β）×γ=（α×γ）+（β×γ）（α×·α）×（β×·β）=（α××β×）·（α×β）α×，β×∈A×B（二十）（48L. Gomes等人/理论计算机科学电子笔记348（2020）43.Σi∈Ii∈Ii∈Ii∈I二十一）图二. [18]第18话h1;h2=h2;h1（22）h;h=h（23）h1+（h1;h2）=h1（24）h1;h2≤h3惠h2≤h1→h3（25）h;hi=（h;hi）（26）.hi其中i表示结合运算符+的迭代版本，并且I是（可能无限的）索引集。我们假设H是完备的，以确保在有限和中刻画模糊同步语言上的运算符·，×和时，所有上确界都存在。这个性质和公理（25）一起保证了每个上确界分布在任意的下确界上，这被用来证明定理4.6。下面的实施例说明L. Gomes等人/理论计算机科学电子笔记348（2020）4349.→∨⊥u不⊥⊥u不uuu不不TTT∧⊥u不⊥⊥⊥⊥u⊥uu不⊥u不→⊥u不⊥不u⊥u不不u不TTT这个结构。例2.4（2-布尔代数）第一个例子是著名的二元结构2=（{T，}，T，→）布尔连接词的标准解释例2.5第二个例子是第三个有值哥德尔链，它用一个显式的符号u表示“ un k n o w n ”（ 或 “ un f i n e d ” ） 。G3=（{T，u，n}，n，n，n，T，→）哪里例2.6（哥德尔代数）另一个例子是standard哥德尔代数哪里G=（[0， 1]，max，min， 0， 1，→）x y=1，如果x≤yy，如果y x3模糊同步语言本节介绍了模糊同步语言的概念，基于C。Prisacariu提出的清晰同步情况[18]。模糊同步语言上的一些操作也被定义。最后，一个地图，解释每个术语的TSKA作为一个模糊同步语言的形式化。读者可以参考模糊逻辑的任何经典介绍，例如[1]，以获得模糊集和模糊语言的标准定义。定义3.1（H-模糊同步语言）设AB是一组基本作用，H是载体H上的CHA，且P = P（AB）\ {P}是AB的所有非空子集（用x，y表示）的字母表. 序列u，v，. . . 我们称之为AB同步字符串，符号代表空字符串。A B上的H-模糊同步语言是H-模糊同步语言的一个元素，即. 函数L：λ → H。然后，我们可以从正则语言理论中归纳出这种设置的标准运算符。 对任意H-模糊同步语言L，L1，L2，以及对所有w∈N，我们定义以下操作：- n（w）=0，对于所有w∈n50L. Gomes等人/理论计算机科学电子笔记348（2020）43Σ.1ΣΣ∗^^^^^- x（w）= 1，如果w=00否则-（L1<$L2）（w）=L1（w）+L2（w）- （L1·L2）（w）=u，vL1（u）;L2（v），其中w=uv 表示串u和v- L（w）=i≥0 Li（w），其中L0（w）=x（w），L（i+1）（w）=（L·Li）（w）- （L1× L2）（w）=u，vL1（u）;L2（v），其中w=u×v定义为：· u×=u=×u· u×v=（xy）（uJ×vJ） 哪里 u=xuJ 和 v=yvJ， 与 x，y∈θ。人们可能会注意到，定义运算符·和×的表达式似乎是相关的。然而，请注意，运算符·涵盖了通过连接较小的单词u和v来构造单词w的所有可能方式，而运算符×则涵盖了通过上面定义的单词u × v的“经典”同步乘积来构造单词w的所有可能方式定义3.2（基本H-模糊同步语言和×− H-模糊同步语言）基本H-模糊同步语言，记为LB，是一个H-模糊同步语言，使得LB（w）=0，只要w∈ AB。一个×− H-模糊同步语言，记为L×，是一个H-模糊同步语言，使得当w/∈A×B时，L×（w）= 0。请注意，A×Bd不包含从操作者构建的任何操作（例如，对于AB={a，b，c}，abc∈/A×B）。在不失一般性的情况下，我们为单例集{ab}写一个b，对任何ab∈AB。此外，表达式a1.an，对于n≥ 1，将在后面表示一个同步串，其中ai∈ n，1 ≤i≤ n。类似于用于将SKA解释为同步集的同态[18]，我们定义了一个映射来将α∈TSKA的项动作解释为H-模糊同步语言。定义3.3（模糊解释）考虑一个映射FISKA：AB<${0，1}→H使得• FISKA（ab）=LB• FISKA（0）=0• FISKA（1）=χ其中LB是基本H-模糊同步语言，使得LB（w）=0，w/= ab.它的扩张FISKA：TSKA→H以其名，以其名，以其名，在术语代数上称为模糊互-F ISKA（α）=FISKA（α），<$α∈AB<${0，1}F ISKA（α+β）=FISKA（α）<$F ISKA（β）F^ISKA（α·β）=F^ISKA（α）·F^ISKA（β）L. Gomes等人/理论计算机科学电子笔记348（2020）4351^^^^^1Σ2F ISKA（α×β）=F ISKA（α）×F ISKA（β）F^ISKA（α）=F^ISKA（α）4模糊自动机本节介绍我们的主要结果。首先，一种新的类型的模糊自动机被定义在一个CHA模型的模糊转换的可能的隶属度值的空间。一个适当的概念，这些排序的自动机的同步产品，然后。本节结束与两个经典结果的概括：• 对于TSKA的每一项α，都存在一个精确接受FISKA（α）的H-NFA• 给定H-NFAM，存在将M映射到SKA的α的函数f，使得F ISKA（α）=L（M）。定义4.1（具有模糊转换的非确定性自动机）对于H上的CHA，基本动作的集合AB，具有模糊转换的非确定性有限状态自动机（H-NFA）是元组M=（X，x，x0，F，δ），其中：• X是一组有限的状态;• P= P（AB）\{N}是输入字母表（即基本动作集合的幂集减去空集）;• x0是初始状态;• F是最终状态的集合• δ：X × H × X → H是模糊转移函数。直觉，δ（x1，a，x2），对于a∈n，可以解释为“输入”的真度a导致从x1到x2模糊转移关系可以通过函数δθ：X×λλ×X→H归纳推广到λ上的自由幺半群λλ，使得对任意x1，x2∈X，δε（x，ε， x）=.1 ，如果x1=x2并且，对于任意x1，x2∈X，w∈N，a∈N，δ（x1，aw，x2）=δ（x1，a，xJ）;δ（xJ，w，x2）x∈X对于任意状态x1，x2∈X和任意词w∈x2，δn（x1，w，x2）可以解释为“词w引起从x1到x2的转变“的真度给定一个具有支持集A的剩余格A，字母表上的模糊语言经典地定义为模糊子集，即函数λ：λ→A[9]。因此，在本发明中，定义4.2给定H上的CHA和H-NFAM=（X，X，x0，F，δ），M识别的模糊同步语言是函数L（M）：0否则52L. Gomes等人/理论计算机科学电子笔记348（2020）43Σ^^X对于w∈N，L（M）（w）=δ（x0，w，x）x∈F我们可以把L（M）（w）解释为“词w引起M从初始状态到最终状态的转变“的真度L（M）（w）是M对w的识别度。现在我们证明了一个关于H-NFA和模糊同步语言的Kleene定理.当自动机是一个与动作α ∈ T SKA相关联的H-NFA时，取一个记为Mα的H-NFA类进行证明.定理4.3对任意作用α∈SKA，存在一个H-NFAMα，它精确地接受FISKA（α）.证据我们为每个正则表达式构造了一个H-NFAMα，该正则表达式由一个基本动作ab∈AB和运算符+，·和构成。然后，我们为同步算子×提供一个类似于[18]中的构造。自动机的每一个转换都被标记为一对（α，δ（xi，α，xj）），0≤i，j≤n，其中α∈TSKA是与导致状态xi和xj之间转换的输入相关的动作，δ（xi，α，xj）∈ H是转换稍微滥用一下符号，让α∈TSKA表示与动作α相关的自动机的输入，这是一个允许更清晰地呈现归纳证明的约定。因此，在本发明中，基本情况：图3中从上到下分别描绘了与ab∈AB，0和1对应的自动机，即Mab，M0和M1 通过定义4.2，很容易看出，这些自动机中的每一个所识别的模糊同步语言分别与F^ISKA（ab）、F^ISKA（0）和F^ISKA（1）精确地一致。开始（ab，δ（x0，ab，x1））0 1开始x0开始x0（第1页）1图3.第三章。表示动作a∈ AB，0和1的自动机。由定义4.2给出了Mab识别的模糊同步语言通过L（Mab）（ab）=δ（x0，ab，x1）=δ（x0，ab，x1）且L（Mab）（w）=0.因此，L（Mab）=F ISKA（ab）。由M0识别的模糊同步语言由L（M0）（w）=0给出，对所有w∈N，这就是F^ISKA（0）。XXL. Gomes等人/理论计算机科学电子笔记348（2020）4353^^另一方面，F^ISKA（α+β） =Lα<$Lβ和（Lα<$Lβ）（α） =δ<$（x1，α，x2），类似地，M1识别的模糊同步语言定义为L（M1）（M）=1，L（M1）（w）=0，对于所有w1=0。 显然L（M1）=F ISKA（1）。归纳案例：图4、图5和图6中所示的自动机Mα+β、Mα·β和Mα分别对应于项α+β、α·β和α。其结构是标准的[6]。开始见图4。 表示动作α+β的自动机。由Mα+β识别的模糊同步语言由下式给出L（Mα+β）（α α）=δα（x0，α α，x5）=δ（x0，α β，x1）;δα（x1，α β，x5）+δ（x0，α β，x3）;δα（x3，α β，x5）=1;δ（x1，α，x2）;δ（x2，，x5）+1;δ（x3，α，x4）;δ（x4，，x5）=δ（x1，α，x2）;1+0;1=δ（x1，α，x2），类似地，对于单词β，L（Mα+β）（α b β）=δβ（x2，β，x3）（Lα<$Lβ）（β）=δ<$（x2，β，x3）和（Lα<$Lβ）（w）=0，其中w F ISKA（α+β）。开始αβ 因此，L（Mα+ β）=开始（第1页）x0x1（α，δ（x1，α，x2））（第1页）x2x3图5：表示动作的α·β。（第1页）（第1页）图6：表示动作的ααMα·β识别的模糊同步语言定义为X1（α，δ（x1，α，x2））X2（第1页）（第1页）x0的X5（，1）（，1）X3（β，δ（x3，β，x4））X4x0的（α，δ（x0，α，x1））X1（第1页）X2（β，δ（x2，β，x3））X354L. Gomes等人/理论计算机科学电子笔记348（2020）43^α^δβ（xβ，v，yβ）当xα=yα∈αFααB0BBi≥0L（Mα·β）（α β）=δβ（x0，α β，x3）=δβ（x0，α，x1）;δβ（x1，α b，x3）=δ（x0，α，x1）;δ（x1，β，x2）;δ（x2，β，x3）=δ（x0，α，x1）;1;δ（x2，β，x3）=δ（x0，α，x1）;δ（x2，β，x3）与之前类似 F^ISKA（α·β）=Lα·Lβ，其中（Lα·Lβ）（w）=δ（x0，α，x1）; δ（x2，β，x3）如果w= α·β 否则为0。因此，我们认为，L（Mα·β）=F ISKA（α·β）。最后，自动机Mα识别由下式给出的模糊同步语言L（Mα）（αα）=δ（x0，，x1）;δ（x1，αα，x3）=1;δ（x1，α，x2）;δ（x2，α，x3）=δ（x1，α，x2）;δ（x2，α，x2）;δ（x2，α，x3）=δ（x1，α，x2）;δ（x2，α，x2）;1=δ（x1，α，x2）;δ（x2，α，x2）对于字m，L（Mαm）（m）=δ（x0，m，x3）=1.哪里F^ISKA（α） =F^ISKA（α）=LαLα（w）=Li（w）=χ（w） +Lα（w） +L2（w） +. .= Lα（αα）+L2（αα）+. = Lα（αα）+Lα（αα）; Lα（αα）+.=Lα（αα）=Lα（α）;Lα（α）=δ（x1，α，x2）;δ（x2，α，x2）如果w = 1，则L=α（w）=χ（χ）=1，否则为0。因此，L（Mα）=FISKA（α）。Q两个H-NFA的同步乘积Mα=（Xα，P（Aα）\{x}，xα，Fα，δα）b0的和Mβ=（Xβ，P（Aβ）\ {x}，xβ，Fβ，δβ），Mα×β=（Xα×Xβ，P（Aα <$Aβ）\ {x}，（xα，xβ），Fα×Fβ，δα×β）哪里BB0 0δα×β：（Xα×Xβ）×（P（Aα<$Aβ）\ {\displaystyle\ {P}}）×（Xα×Xβ）→H定义为，对于u∈ P（Aα）\{n}和v∈ P（Aβ）\{n}，w=u<$v，由Bδα×β（（xα，xβ），w，（yα，yβ））=Bfxβ=yβ∈Fβu，vδα（xα，u，yα）;δβ（xβ，v，yβ）L. Gomes等人/理论计算机科学电子笔记348（2020）4355B0B相应的构造在图7中示出。定义4.4设Mα=（Xα，P（Aα）\{x}，xα，Fα，δα）和Mβ=（Xβ，P（Aβ）\{x α，Fα，δ α}）{x}，xβ，Fβ，δβ） 被两H-NFA和Mα×β=（Xα×Xβ，P（Aα<$Aβ）\0B B56L. Gomes等人/理论计算机科学电子笔记348（2020）43F^0000FF00FFF{f}，（xα，xβ），F α× F β，δα×β）的同步积。 模糊同步局域网Mα×β所识别的规范是函数L（Mα×β）：P（Aα<$Aβ）\{n} →H定义的B B通过L（Mα×β）（w）=λ.δα×βε（（xα，xβ），w，（xα，xβ））.00 ffxα∈Fαxβ∈Fβ类似于其他情况，我们证明了Mα×β识别模糊同步语言F^ISKA（α×β）：L（Mα×β）（α×β）=（δα×β）（（xα，xβ），α×β，（xα，xβ））=δα×β（（xα，xβ），α×β，（xα，xβ））=δα（xα，α，xα）;δβ（xβ，β，xβ）0f0fα αββ αβ但F^ISKA（α×β）=Lα×Lβ，满足（Lα×Lβ）（w）=δ（x0，α，xf）;δ（x0，β，xf）如果w=α×β，否则为0。因此，L（Mα×β）（α×β）=F^ISKA（α×β）。开始开始×开始−→x1，x3x1，x4S1S2x2，x3x2，x4见图7。 对应于α×β的自动机构造示例。其中，s1表示标签（α，δα（x1，α，x2）），s2表示标签（β，δβ（x3，β，x4）），s表示标签（α×β，δα×β（（x1，x3），α×β，（x2，x4）对应于同步动作α×β。证明了SKA w.r.t.模糊解释通过消除产生正则表达式的状态来考虑一个函数f，它取一个H-NFAMα，返回一个动作α∈SKA. 与之相关的权重 根据自动机的每个转换的权重，相应地计算该动作。请注意，此过程将SKA的操作视为自动机转换的标签，而不是输入字母表的元素定理4.5对于所有α ∈TSKA，f（Mα） 结果是一个动作α，F ISKA（α）= L（Mα）。证据 证明使用归纳法的行动的结构。基本情况：让我们考虑图3中的自动机Ma、M0和M1。应用f，我们得到动作a，0和1，分别具有权重δ（x0，a，x1），0和1。归纳案例：情况α=α1+α2。自动机Mα1+α2是由自动机Mα1和Mα2通过定理4.3中的+的构造得到的。然后，f消除状态X1S1X2X3S2X4L. Gomes等人/理论计算机科学电子笔记348（2020）4357x1和x2，获得由动作1·α1·1 <$α1标记 的单个转 变，权重为1; δ（x1，α1，x2）; 1 = δ（x1，α1，x2），以及状态3和4，获得由动作1·α2·1 <$α2标记的单个转变，权重为1; δ（x3，α2，x4）; 1 = δ（x3，α2，x4）。最后，它将这两个转换组合成一个标记为动作α1 + α2的转换，其权重为δ（x1，α1，x2）+ δ（x3，α2，x4）。开始开始开始图八、 f在自动机Mα+β，Mα·β和Mαβ中的应用情况α=α1·α2。自动机Mα1·α2由Mα1和Mα2通过定理4.3的过程获得。通过消除中间态x1和x2，我们得到一个标记为α1·1·α2<$α1·α2 的单个跃迁，其权重为δ（x0，α1，x1）;1;δ（x2，α2，x3）=δ（x0，α1，x1）;δ（x2，α2，x3）。情况α= α1π。使用相同的方法，f消除M α 1 的 状态x1和x2， 从而得到具有由y1·α1·（1·α1）n·1+1nα1n 标记的单个转移的自动机，其中weigt1;δ（x1，α1，x2）;（1;δ（x1，α1n ，x2））; 1+1=δ（x1，α1，x2）;δ（x1，α1n，x2） +1。通过上述情况的过程获得的结果自动机如图8所示。情况α = α1× α2。类似地，函数f消除状态（x1，x4）和（x2，x3），得到具有单个转移的自动机，标记为带权的α×βδα1（x1，α1，x2）;δα2（x3，α2，x4）=δα1×α2（（x1，x3），α1×α2，（x2，x4））。Q接下来，我们将模糊同步语言集作为一个SKA。定理4.6任何一组包含X和X且在定义3.1的运算下封闭的模糊同步语言，对于任何CHA，都是一个同步Kleene代数。证据（1）-（13）的证明类似于[5]。 注意，在[5]中，代替（12）和（13），等价公理α·γ≤γ <$α<$·γ≤γ和γ·α≤γ<$γ ·α<$≤γ。我们目前只证明公理处理运营商×，对于一个给定的词1. an∈ N，其中n ≥ 1。公理（14）：x0的α1+α2X5x0的α1·α 2X3x0的α1∗X358L. Gomes等人/理论计算机科学电子笔记348（2020）43={x的定义..-是的- 是的ΣΣΣΣΣk≥1l≥1k≥1l≥1k≥1l≥1（L1×（L2× L3））（a1. a n）={x的定义k≥1（L1（a1. . . an）;（L2×L3）（a1. . . ak）+L1（a1. . . ak）;（L2×L3）（a1. . . a（n））- 是的L1（a1. . . an）;. （L2（a1. . an）;L3（a1. . . a1）+L2（a1. . . a1）;L3（a1. . .an））+L1（a1. . . ak）;. （L2（a1. . an）;L3（a1. . . a1）+L2（a1. . . a1）;L3（a1. . . an））={（26）和（5）}好吧（L1（a1... a n）;（L2（a1. a n））; L3（a1. a 1）+（L1（a1. a n）; L2（a1... a l））;L3（a1. a n）+100。（L1（a1... a k）;（L2（a1. a n））; L3（a1. a 1）+（L1（a1. ak）; L2（a1. al））; L3（a1. a n）={（27）并不失一般性地更改索引}好吧（L1（a1... ak）; L2（a1. a1）+L1（a1. a l）; L2（a1. a k））; L3（a1.. a n）+（L1（a1. a n）; L2（a1... a 1）+（L1（a1. a l）; L2（a1. a （n））l≥1L3（a1. a k））; L3（a1..（a、k）={x的定义k≥1（L1× L2）（a1... ak）; L3（a1. an）+（L1× L2）（a1. a n）; L3（a1. （a、k）={x的定义（（L1×L2）×L3）（a1... a n）公理（15）：（L1× L2）（a1. a n）={x的定义（L1（a1... a n）; L2（a1... a k）+L1（a1. ak）; L2（a1. a （n））k≥1={（2）和（22）}（L2（a1. a n）; L1（a1. ak）+L2（a1. a k）; L1（a1. a （n））k≥1={x的定义（L2× L1）（a1. a n）公理（16）：（L × χ）（a1. a n）={x的定义（L（a1. a n）; x（a1. a k）+L（a1. a k）; x（a1. a （n））k≥1={x和（6）的定义}l≥1l≥1ΣΣL. Gomes等人/理论计算机科学电子笔记348（2020）4359（L（a1. a n）+L（a1…a k））= L（a1. a n）x的定义k≥1χ×α也可以用类似的方法证明60L. Gomes等人/理论计算机科学电子笔记348（2020）43Σ-是的Σ-是的（定义）- 是的Σ- 是的Σ- 是的Σ11n21K11n31ΣKk≥1l≥0l≥0公理（17）：（L×）（a1. a n）={x的定义公理（18）：这个公理只适用于基本的模糊同步语言LB。因此，给出了一个基本的模糊同步（L（a1k≥1... a n）;a1...（a、k）语言LB，（LB× LB）（ab）+ L（a1. a k）; n（a1. a（n））（9）（）（）={x的定义k≥1LB（ab）;LB（ab）0k≥1（23）k≥1LB（ab）={x的定义（a1. a n）对α×α的证明使用了类似的推理。公理（十九）：（L1×（L2<$L3））（a1. a n）={x和x的定义}L1（a1. a n）;（L2（a1. ak）+L3（a1. a（k））k≥1+ L1（a1. a k）;（L2（a1. a n）+L3（a1... a（n））（7）={x的定义LB（ab）（2）L1（a1. a n）; L2（a1... （a、k）k≥1+ L1（a1. ak）; L2（a1. a n）+ L1（a1. a n）; L3（a1. （a、k）- 是的L（a）... a）;L（a... a）+L（a）...a）;L（a. a）、k≥1+ L1（a1. ak）; L3（a1. a n）={x和x的定义+ L1（a1. ak）; L2（a1. a n）+L1（a1. ak）; L3（a1.an）公理（20）：类似于（19），但使用（8）。（（L1× L2）（L1× L3））（a1. a n）公理（21）：这个证明是通过考虑×-模糊同步语言完成的。（（L×1·L1）×（L×2·L2））（a1. . . an）={x的定义k≥1。（L×1·L1）（a1. . . an）;（L×2·L2）（a1. . . ak）+（L×1·L1）（a1. . . ak）;（L×2·L2）（a1. . . an）- 是的. �L1×（a1. . . al）;L1（al+1. . . an）n;. �L×2（a1. . . al）;L2（al+1. . ak）+的版本。�L1×（a1. . . al）;L1（al+1. . . ak）a;。�L×2（a1. . . al）;L2（al+1. . an）l≥0={L×（a1.对于k = 1，a k）= 0}l≥0k≥1（L×1（a1）;L1（a2. . . an））;（L×2（a1）;L2（a2. . . ak））+（L×1（a1）;L1（a2. . . ak））;（L2×（a1）;L2（a2. . . a（n））={（5）和（22）}k≥1（L1×（a1）;L×2（a1））;（L1（a2. . . an）;L2（a2. . . ak））+（L×1（a1）;L×2（a1））;（L1（a2. .ak）;L2（a2. . a（n））（7）k≥1（L×1（a1）;L×2（a1））;（L1（a2. . . an）;L2（a2. . . ak） +L1（a2. . . ak）;L2（a2. . a（n））ΣL. Gomes等人/理论计算机科学电子笔记348（2020）4361- 是的Σ={x和L×的定义（a1.对于k = 1，a k）= 0}k≥1（L×1×L×2）（a1. . . an）;（L1×L2）（a2. . . an）（定义）（（L×1×L×2）·（L1×L2））（a1. . . an）Q62L. Gomes等人/理论计算机科学电子笔记348（2020）43X1CX2^^让我们重新回顾一下引言中提到的关于两种试剂的联合模糊流流程中的模糊性表示控制设备中的潜在故障为了模拟执行的置信度值，我们假设例2.6的结构G。例如，考虑机器以确定性值0释放试剂c和m。95和0。93、分别我们通过采取与确定性增加c相0。95和增加m的动作，确定性为0。93中描述的两个H-NFA，图9，其中c表示标签（c，δc（x0，c，x1）），类似地，m表示标签（m，δm（x0，m，x1））。入门开始见图9。 两个H-FA代表基本动作c和m.让我们考虑一台机器能够同时执行动作c和m。其行为由上述自动机的同步乘积建模，结果如图10所示，其中c，m表示标记（{c，m}，δc×m（（x1，x3），{c，m}，（x2，x4）。开始见图10。 同步产品。对应于获得两种试剂混合物的确定性的作用权重c×m由下式给出：δc×m（x1，x3），{c，m}，（x2，x4）= δc（x1，c，x2）; δm（x3，m，x4）=min{0. 95，0。93}= 0. 935结论在这项工作中，我们定义了模糊同步语言的概念，这些语言上的一些运算符，以及两个H-NFA的同步乘积构造证明了两个经典结果的推广：对TSKA的每一项α，都有可能构造一个精确接受FISKA（α）的H-NFA;对所有α∈TSKA，存在一个映射Mα到SKA的α的函数f，使得FISKA（α）=L（Mα）. 最后，我们证明了任何一组用前面定义的模糊算子丰富的模糊同步语言都是SKA。X3MX4x1，x3x1，x4Cx2，x3Mx2，x4
我的内容管理
展开
