业务流程管理中的分散执行：LSAWfP模型强调参与者观点的进程指定

沙特国王大学学报一个强调参与者观点的分布式执行管理过程Milliam Maxime Zekeng Ndadjia，b， Maurice Tchoupé Tchendjia，b，Clémentin Tayou Djamegnia，Didier Parigotca喀麦隆Dschang大学b法国FUCHSIA研究联合小组cINRIA，Sophia Antipolis，法国阿提奇莱因福奥文章历史记录：收到2021年2021年7月6日修订2021年7月25日接受在线预订2021年关键词：行政流程规划语法视图LSAWfPA B S T R A C T在业务流程管理中，业务流程的分散执行是主要的研究课题之一。已经提出了几种用于过程建模的模型，以促进其执行。LSAWfP是这一领域的最新成果之一：它有助于指定具有语法模型的管理流程，在本文中，我们提出了一个模型，一个完全分散执行的进程指定使用LSAWfP。所提出的模式强调行为者的观点：然后，通过确保每个参与者潜在地具有对过程状态的部分感知，它允许某些任务的机密执行。因此，该模型解决了业务流程执行中经常被忽略的问题。为了实现这一点，它依赖于三个投影算法，允许部分复制进程的全局执行状态（工件投影算法），以consistently更新所获得的部分状态（模型投影算法），并推导出新的连贯的全局状态（扩展修剪算法）。这些算法的提出、底层数学工具版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY许可下的文章（http://creativecommons.org/licenses/by/4.0/）。1. 介绍行政业务流程是指所有案例都是已知和可预测的流程（Van DerAalst，1998）（同行评审、保险索赔等）：它们在实践中最常遇到（Van Der Aalst，2013; Dumas等人，2018年）。在其最广泛的方法中，业务流程管理（BPM）技术将给定业务流程的自动化分解为工作流语言中的正式规范（建模）（Dumas等人， 2018）;由此产生的工作流程模型通常*通讯作者：喀麦隆Dschang大学。电子 邮件 地址： ndadji. univ-dschang.org （ M.M.Zekeng Ndadji） ， maurice.univ-dschang.org （ M.Tchoupé Tchendji ） ， dtayou@yahoo.com （ C. 塔 尤 · 贾 梅尼），迪迪埃·帕里戈特@ inria.fr（D。Parigot）。网址：https://project.inria.fr/fuchsia/（M.M.Zekeng Ndadji），https：//project.inria.fr/fuchsia/（M. Tchoupé Tchendji）。沙特国王大学负责同行审查描述了所有流程对于以任何工作流语言描述的管理过程的分散执行，可以想象由多个反应性代理或对等体组成的分布式工作流管理系统（WfMS），由人类代理（负责执行任务的演员）驱动，使用他们合作编辑的工件彼此协调。事实上，行政流程的分布式执行类似于一个表单的合作版本，该表单必须从一个站点分发到另一个站点（移动表单），以便由流程的不同参与者进行编辑。在它到达站点时，与站点相关联的参与者必须能够检查它，并毫无歧义地推断出已经编辑的字段（这些对应于流程中已经执行的任务），他必须立即编辑的字段（这些对应于他必须执行的就绪任务），并且可能地，他必须返回/重定向表格以便在其编辑结束时进一步处理的站点。很容易想象，可能存在需要由不同参与者填充的具有独立字段的表单。在这种情况下，为了加速处理，可以接受的是，在给定的https://doi.org/10.1016/j.jksuci.2021.07.0191319-1578/©2021作者。由Elsevier B.V.代表沙特国王大学出版。这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comM.M.Z. Ndadji，M.T.Tchendji，C.T.Djamegni等人沙特国王大学学报61053.ΣKK同时，在系统中可能存在被同时编辑的表单的多个副本行政过程的一个主要特征是保密性：并非行政过程中的所有参与者都必须了解该过程中产生的所有处理和/或数据。因此，很自然地认为，在站点上呈现给参与者进行编辑的表单只是全局形式;1该（部分）复制品仅包含被考虑的参与者所证实感兴趣的信息（与处理和数据有关）一旦收到表单的部分副本，就必须确保其上的所有编辑操作都可以一致地集成到全局表单中。为了满足这一约束，每个演员都有一个本地的“监督者”，他必须控制他的编辑动作。某些任务的机密执行以及对某些过程数据的访问限制在现有的BPM方法中通常很少解决。大多数确实提到这些方面的研究，要么将它们降级到第二位，要么不像其他方面那样正式对待它们。在这项研究中，重点是这些问题。上面两段中描述的形式可以被看作是一个结构化的文件（一棵树），从一个网站传播到另一个网站，通过在其叶子一级制作的合作版本（正面版本2）来扩展。因此，这棵树的节点要么代表已经执行的任务，要么代表准备执行的任务;此外，节点之间的关系（父子，兄弟）完全对应于任务的顺序。在以工件为中心的业务流程建模方法中，这棵树被称为基 于 在 （ Badouel 和 Tchoupé Tchendji ， 2008; TchoupéTchendji 等 人 ， 2017 年 ; Tchoupé Tchendji 和 Zekeng Ndadji ，2017年; Zekeng Ndadji和Tchoupé Tchendji，2018年），我们在本文中提出了一种用于管理过程的分布式执行的模型（工件的合作版本），该模型依赖于算法来获得：（1）全局工件的部分副本（工件投影算法）;这些副本仅包含与所考虑的参与者相关的信息;（2）约束局部工件上的局部编辑操作的局部模型（模型投影算法），以确保（3）这些始终是“可扩展的”作为全局工件上的编辑操作（更新）（扩展-修剪算法）。所提出的执行模型仅适用于使用语言LSAWfP（管理工作流过程规范的语言）获得的过程模型（Ndadji等人，2020年a、b、c）。LSAWfP是一种新的语言，旨在规范（使用属性语法的变体）的行政流程，特别强调的是建模（使用视图）的看法，各种行为者对流程及其数据。在这种语言中，特定进程的规范由三元组（语法模型）行政工作流程- GMAWfP -）Wf 1/4。G;LP;LA1) 算法的建议：- 工件●模型全局模型G，以导出局部模型GVi。GVi将指导给定参与者在其站点的部分副本上执行的操作，以确保与全局模型G的一致性。●扩展修剪;这使得逆投影由给定参与者Ai根据以下更新的部分副本tmajVi到局部模型GVi;目标是将由局部参与者做出的贡献集成到符合全局模型G的工件tf中。2) 使用所提出的算法时，工件及其模型的稳定性特性的研究3) 一个Haskell实现所提出的算法。手稿的组织：在本文的其余部分，我们简要介绍了LSAWfP语言和一个使用它建模的过程的例子（第2.2节）。然后，我们提出了本文中考虑的以人为中心的流程执行模型，以激发提出稳定投影算法的需求（第2.3节）。我们继续提出本文所涉及的三种投影算法的版本，以及对它们的一些性质的研究（第3节）。最后，我们进行了讨论并得出结论。2. 使用LSAWfP已经开发了几种工具来解决过程建模问题。其中最著名的是BPMN标准（业务流程模型和符号）（模型，2011年），它使用从状态图的形式主义派生的形式主义，以及基于Petri网的YAWL语言（另一种工作流语 言 ） （ Van Der Aalst 和 TerHofstede ， 2005; Van Der Aalst ，2013）。在本节中，我们介绍了新兴语言LSAWfP（Ndadji et al.，2020a，b，c）及其说明：管理过程的规范用作本文的运行示例。为了激励当前的工作，还提出了以工件为中心的执行模型LSAWfP2.1. 一个正在运行的例子：同行审查程序同行评审过程是业务过程的一个常用示例，用于说明工作流语言（Ndadji等人，2020年a、b、c）。我们在这份手稿中选择它是因为它很容易G是任务及其排序的模型，LPk和LAk分别代表演员名单和他们的认证。如果我们考虑GMAWfPWfG;LPk;LAk以分散的方式执行，则本文的主要贡献如下：1总表载有系统内各行动者迄今为止已填写的所有数据因此，它通过显式突出显示已编辑的字段、准备立即编辑的字段和稍后将编辑的字段（在字段之间存在依赖关系的情况下），给出流程2在阳图版中，没有信息被擦除。对文档的编辑操作会通过在其叶子级别添加子树来使表示文档的树增长。[3]对给定参与者的认证提供了与所研究过程的每种类型（任务）相关的权利（许可）信息描述和（这是最重要的）它完美地说明了我们处理的概念。我们考虑的描述与Ndadji等人（2020 a）中的描述相同：该过程涉及四个参与者（一个主编-EC-，一个助理编辑-AE-和两个裁判-R1和R2 -）协调评估提交给他们审查的手册（论文）。这一过程从欧盟委员会收到文件时开始;收到后，EC对文件进行预验证（我们称之为“A”）;在预验证后，他可以接受或拒绝各种原因（次要兴趣的主题，论文不在期刊范围内，格式不符合等）的论文;如果他拒绝论文，他写一份报告（任务● 否则，他选择一个AE并将论文发送给他●●●其中，●M.M.Z. Ndadji，M.T.Tchendji，C.T.Djamegni等人沙特国王大学学报6106● S！！KK● A SKK！¼助理工程师准备稿件（任务"C“），组成一个评审委员会（在我们的案例中是两名每位裁判员阅读并认真评估论文（任务在收到所有推荐人的报告后， AE 做出决定并通知EC （任务"F“），EC将2.2. 使用LSAWfP进行LSAWfP是一种专门为行政流程建模而设计的新兴语言。它依赖于属性语法的一个变体，为这些过程的主要概念方面的建模提供了一个框架：这些方面涉及任务此外，LSAWfP特别强调各种利益攸关方对流程及其数据的看法的建模（使用观点），以保证保密性。要使用LSAWfP对给定的流程进行建模，必须遵循四个关键步骤：（1）使用带注释的树对流程场景进行建模;（2）从带注释的树中派生出一个抽象语法，该语法将用作生命周期模型;然后（3）识别流程执行中涉及的参与者;（4）使用认证列表确定每个参与者所扮演的角色。2.2.1. 使用工件LSAWfP建立在这样的原则上：根据定义，所有执行场景、所有参与者以及他们在给定管理过程Pad的任务中所扮演的角色都是预先已知Fig. 1. 给定过程（同行评审过程）的目标工件示例。生产p是的一的的以下两形式：p：X0X1;...; X n或p：X0X1. Xn.这两种形式的产品完美地模拟了目标工件设计中保留的两种类型的排序（并行或顺序）。在这种情况下，每个目标工件ti符合G，我们记为ti）G;不同目标工件的根符号也构成G的公理集。GMWf可正式定义如下：定义2.1.工作流语法模型（GMWf）由GMWf定义，其中：是与要在所研究的业务流程中执行的各种任务相对应的语法符号或排序的有限集合;语法符号是称为公理的特定符号的有限集合，表示可以启动执行场景的任务（tar的获取工件），以及● PS× Sω是一个由注解“;“（顺序于）和"k“（平行于）修饰的有限产生集因此，LSAWfP建议对每个广告的执行场景进行优先规则一生产P¼XP0;XP1; ···XPP是使用被称为目标人工制品的注释树T。在这样一棵树上，要么的的表格P：X！ X;. X.ðÞðÞ吉吉吉节点（标记为Xi）潜在地对应于Pad的任务Xi，并且01jPj，或的形式每个分层分解（节点及其子节点）对应于调度：与父节点相关联的任务必须在与子节点相关联的任务之前执行;子节点必须根据顺序（并行或顺序）执行，该顺序可以由将应用于每个分层分解的特定注释注释‘‘ ”) reflects the fact that the 可以）按顺序（分别）执行并行）。 在顺序排序（X1;...; X n），最左边的任务必须在它们右边的任务之前执行（X i必须在X j之前执行 如果j>i）。对于正在运行的示例（同行评审过程），只有两种执行场景：一种是EC立即拒绝论文，另一种是论文经过验证过程。这些可以使用图1中的两个工件art1和art2来建模。特别是，我们可以看到，图1显示了分配给EC的与符号A（见第2.1节）相关的任务2.2.2. 工作流语法模型GMWf的在使用目标工件对所研究的过程的场景进行建模之后，LSAWfP建议从它们中提取一种抽象语法，称为工作流语法模型（GMWf）。这是通过简单地将目标工件的集合替换为语法标记G（GMWf）来完成的，其中，每个符号指代一个任务，并且每个P：X0！X1K... kXjPj和jPj表示P右边的长度.一个符号为X的产生式称为X-产生式。考虑到同行评审过程的情况，其目标工件在图1中表示，导出的GMWf为G;S;P;A，其中语法符号的集合S是S ¼ fA;B;C;D;E;F;G1;G 2;H 1;H 2;I 1;I 2g（见第2.1节）;唯一初始任务（公理）是A（则A ^fAg），生成集P是：P1：A！ B; D P2：A！ C; DP3：C！ E; F P4：E！G1KG2P5：G1！ H1; I1P6：G2！ 氢，碘P7：B！ eP8：D！ eP9：F！ e P10：H 1！ eP11：I 1！e P12：H 2！ eP13：I 2！e注意，形式Xe的产生表示在某些执行场景中，任务X可以被执行并且不能被开发成其他任务;因此，X在以下中的目标文物2.2.3. 确定进程的行为者在文本描述的帮助下，很容易确定参与执行该过程的行为者。例如，根据对同行评审过程的描述，四个（k4）参与者参与其执行：主任（EC），一名助理编辑（AE）和两名审稿人（R1和R2）。 所以我们推断出参与者的列表是LPk 1/4 fEC;AE;R1;R 2g。●●●M.M.Z. Ndadji，M.T.Tchendji，C.T.Djamegni等人沙特国王大学学报6107V 2 V.我我我我KK2.2.4. 建立认证名单LSAWfP建议采用一种称为认证的机制，其灵感来自Unix类系统中使用的权利术语，以确保行为者之间更好的协调，并最终保证某些行动和数据的保密性。一个给定的行为者的认证提供了关于其权利（许可）的信息，相对于研究过程的GMWf的每一种（任务）有三种类型的认证：1. 在阅读（r）中的认证：在X类阅读中认证的行为者必须自由访问其执行状态（在其执行期间生成的数据）。一个演员在阅读中被认可的那一套被称为他的观点。任何属于给定视图i（Xi）的排序X都被称为可见的，而那些不属于它的则被称为不可见的。2. 书面认可（w）：在X类上书面认可的行动者可以执行相关任务。4.任何以书面形式被认可的行为者都被认可为阅读者。只有一个行为者才能以书面形式被认可为阅读者。3. 执行中的认可（x）：在X类的执行中认可的行为者被允许要求在其中以书面形式认可的行为者执行它。更正式地说，认可定义如下：定义2.2.在演员Ai的语法符号集合S上定义的认证AAi是三元组AA AAAr;AAw;AAx表1参加同行审查进程的不同行为者的资格认证总编辑（EC）AEC^fA;B;C;D;H1;H 2;I 1;I 2;Fg;fA;B;Dg;fCgAssociated Editor（AE）AAE¼ fA;C;E;F;H1;H 2;I 1;I 2g;fC;E;Fg;fG 1;G 2g第一裁判员（R1）AR1¼fC;G1;H1;I1g;fG1;H1;I1g;E第二个参考文献（R2）AR2=C;G2;H2;I2g;FG2;H2;I2g;Edigm。根据它，工作流管理集中在自动化的过程和使用业务工件的概念操纵的数据。业务工件被认为是一个文档，它传达了关于特定业务流程执行情况的所有信息，从系统中的开始到结束。在本节中，我们将为受GMAWfP启发的分布式执行提供一个以工件为中心的模型。通过Badouel等人关于结构化文档的合作编辑的工作（Badouel和TchoupéTchendji，2008; TchoupéTchendji等人，2017; Tchoupé Tchendji和Zekeng Ndadji ， 2017;Zekeng Ndadji 和 Tchoupé Tchendji ，2018）。我们首先分别介绍执行模型的关键概念，然后再研究分布式系统的整体行为2.3.1. 执行模式执行环境。要在中执行给定的GMAWfP，分散模式，我们考虑一个完全分散的工作流管理系统这样，AAirs也称为演员Ai的视图，是符号集其中Ai被认可为阅读，AAiwAir是Ai被认可为书写的一组符号，AAixs是Ai被认可为执行的一组符号根据运行示例中同行评审过程的任务分配，可以得出EC的书面认证是AEC认证;B;Dg。此外，由于他只能在任务C（由AE执行）已经执行的情况下执行任务D（参见图1中的第1条和第2条），因此他必须被授权执行C才能请求执行C;因此，我们有AECxfCg。此外，为了能够访问同行评审评估（任务C）进展的所有信息并综合要返回的正确决定，EC必须能够查阅裁判的报告（任务I1和I2）和消息（任务H1和H2），以及AE做出的决定（任务F）。这些任务，除...关于ECw5 构成集合AECrVECfA;B;C;D;H1;H 2;模型（我们称之为P2P-WfMS-View），其实例（对等体）安装在流程执行中涉及的各种参与者的站点在流程执行期间，这些对等点通过交换正在执行的（全局）工件的副本进行通信（发送/接收请求/响应）。这样的工件提供了关于已经执行的任务和准备执行的任务的信息。正如Badouel和Tchoupé Tchendji，2008年; TchoupéTchendji等 人 ， 2017; Tchoupé Tchendji 和 Zekeng Ndadji ， 2017;ZekengNdadji和Tchoupé Tchendji，2018），我们通过包含芽的树（结构化文档）表示正在执行的工件。这些表明在一个时刻，唯一的地方，捐款是预期的。根据相应的任务（节点）是否准备好执行（编辑），可以解锁或锁定bud芽是分型的;X2S型的芽是叶节根据其状态（锁定或未锁定），标记为Xx或XxI1;I 2;Fgð Þ他在阅读中被认可的任务这样做了锁定）（见图 2）的情况。因此，特定行为体的地方行动将其他参与者中的每一个导致表1中表示的认证的扣除，并且我们有LAk1/4 fAEC;AAE;AR1;AR2g。最后是管理工作流过程的语法模型：使用LSAWfP，过程建模的结果是一个三层语法模型。plet Wf¼.G;LP;LA（称为管理的语法模型）具有通过经由适当的产品开发其所包含的不同的解锁芽来扩展（编辑）其所接收的（全局）人工制品的副本的效果保密地执行某些任务。出于保密的原因，每个参与者作用于（全局）工件的本地副本：此部分副本仅包含其中，G是GMWf，LPk是演员和L AK的名单 是他们的认证名单2.3. 一种以工件为中心的GMAWfP分布式执行模型以工件为中心的范式出现于21世纪初，在过去的二十年里，它已经成为流程建模和执行（工作流管理）最受欢迎的思想潮流（Van DerAalst，2013）。几项工作（Nigam和Caswell，2003年; Hull等人，2009; Lohmann和Wolf，2010;Badouel等人， 2015年，为发展这一...4让5请记住：任何被认可在某种类型上写作的行为者都被认可在阅读它。相关行为者可以访问的信息从技术上讲，人工制品t的部分副本tVi是通过根据相关演员的视图Vi投影 t （ 使 用 人 工 制 品 投 影 的 算 子 p ） 获 得 的 ： 我 们 记 为 tViI'msorry.I'msorry.每个站点都需要一个本地GMWf由于特定参与者的局部要做到这一点，必须推导出一个本地的GMWf在每个网站上，根据当地的演员（GMWf投影）的观点，通过投影的全球该投影使用P算子进行，得到的GMWf记为GVi I'm sorry.I'msorry.扩张行动。为了确保系统的安全性，项目趋同，即特定行为体和国家所作的贡献保留在更新的部分副本tmaj中，必须集成到ViM.M.Z. Ndadji，M.T.Tchendji，C.T.Djamegni等人沙特国王大学学报6108V2A..ΣΣ第四季）图二.一种包含花蕾的注释人工制品的有意表示。在对等体之间进行任何同步之前，创建（全局）工件的本地副本。因此，有必要能够合并这两个工件，这是基于两个不同的模型。我们在这里找到了Badouel和Tchoupé Tchendji（2008）中表述的膨胀问题的一个版本。2.3.2. 执行模型和对等活动然 后 ， 在 全 局 上 ， 在 给 定 过 程 的 执 行 之 前 ， 使 用 其GMAWfPWf^G;LPk;LAk来配置对等体。从全局GMWf G和本地参与者的视图Vi，每个对等体通过投影导出本地GMWfGVi 。 I'm sorry.I'msorry. 然后，当工件t被引入系统（在适当的对等体上）时，过程案例的执行被触发;该工件实际上是（全局）GMWf G的一个公理AG（初始任务）类型的未锁定芽（见图1）。 3）。在执行过程中，对等点通过交换它们正在执行的工件的本地副本来同步它们自己。在给定对等体上接收到工件t）G之后，后者将其与其本地副本合并，然后将其投影（参见图1中的对等体i）。 3）根据局部视图Vi.然后在需要时完成（编辑）所获得的部分副本tVi）GVi：该编辑的结果是伪像t_maj）GV，例如t_maj是t_V（t_maj_P_t_V）的更新。3. GMAWfP分布式执行的投影算法GMAWfP执行模型主要基于三种算法：工件投影、GMWf投影和扩展。在本节中，我们提出了这些算法的版本，以及它们的一些数学性质的研究，保证correc- tion的执行模型，和一致性的分布式系统所形成的对等端负责执行一个给定的GMAWfP。3.1. 伪影投影算法3.1.1. 该算法从技术上讲，通过在t中删除其类型不属于i的所有节点（所有不可见节点）来获得伪影t根据视图Vi^Ai^r的投影tVi在我们的案例中，该操作中的主要挑战是：(1) tVi的节点必须保持它们之间在t中先前存在的执行顺序，(2) tVi必须通过专门使用为GMWf保留的仅有的两种生产形式来建造，(3) tVi 必须是唯一的，以确保过程执行的连续性（见第2.3.2节）。投影运算记为p。受Badouel和Tchoupé Tchendji（2008）提出的一个启发，它投射了一个艺术，保留工件节点之间的层次结构（父子关系）的事实（因此它满足挑战（1））;但是此外，在必要时，它将新的附加（重构）结构符号（可由为其进行投影的代理以读写方式访问）插入到投影的人工制品中。这使它能够应对挑战（2）。在提出算法（算法1）之后，立即概述了如何完成挑战（3）的细节。图图4示出了相对于R1（第一裁判）和EC（主编）视图的同行评审过程的工件的投影。注意在tVEC中存在新的（重新）结构化符号（灰色）。最后这些使避免引入tVEC，生产p：C！H1;I 1kH 2;I 2;F，其形式与GMWf写作中保留的两种生产形式8让我们考虑一个伪影t，记为n<$X½t1;.。 . ;tm]标记有符号X并且具有m个子伪像t1，. ;tm.还请注意p n，用于扩展节点n的GMWf的产生; p n的类型是顺序的（即p n的形式为p n：X！X1;.. . ;X m，其中X1;. ;X m是子伪影的根。 ; t m）或平行（p n：X！ X1k.. . kX m）。具体地说，根据给定的视图投影t(i.e寻找项目pVt），a执行t的深度路径，并擦除不可见节点，或者ViiVi我VII由与（重新）结构化符号相关联的新节点替换在完成的最后，获得更新的部分副本tmajGViVi 是为了获得以保持子树结构。为此，递归过程-在算法1中提出的，被应用于根节点（全局）工件本地副本的更新配置t f）G（参见图1中的对等体i）。3）。如果最终的配置显示该过程应该在其他站点继续，那么将工件的副本发送给它们。否则，将复制品返回给先前从其接收到工件的对等体n<$X½t1;.. . ;tm]oft.6当工件包含在当前对等体上创建的芽时，其演员的书面认可是在遥远的同行。7工件是完整的（它不再包含芽），或半完整的（它包含在其他对等体上创建的芽，并且当前对等体上的演员没有书面认可）。[8]请注意，这个产生式在它的右边指定了我们必须有并行和顺序的处理。 插入S1、S2和S3允许在四个产品中重写p 1：C！ S1; F; p 2：S 1！ S2 kS 3; p 3：S 2！H1; I 1和p 4：S 3！ H2; I 2.M.M.Z. Ndadji，M.T.Tchendji，C.T.Djamegni等人沙特国王大学学报6109ΣΣVi●2V..hi图三. 给定进程的分布式执行概述。见图4。 在人工制品上进行投影并获得部分复制品的示例。执行模式的一致性还应注意，该算法算法1：根据给定视图如果符号X可见（X），则：1. n保存在工件中;2.）的情况。对于n中的每个子工件ti，具有节点n1/2Xi i i1;. ;tik作为根（其中pni是用于扩展它的产生式），应用以下处理a. t的投影根据。得到了n o列表项目 1/2V1;. . ;tiVl;可以返回多个工件（一个森林）。为了避免它在某些情况下产生森林，从而满足挑战（3），我们做出以下假设：在这项工作中操纵的GMAWfP是这样的，即所有参与者都被认可阅读GMWf公理（公理相对于假设）。因此，设计者必须确保所有参与者都能阅读所有GMWf公理。为了做到这一点，在建模之后，一过程Pad和获得其GMWfG/S;P;A，如果有必要，创建一个新的公理一个G上，所有的演员将被认可的阅读，并协会-吃了它与新的单位制作9pa：AG！其中，Xa2A是b. 如果pni的类型 与pn的类型相同，ti的投影产生的伪影不超过一个（项目I） 61），我们仅用伪影t iV1;. ;t iVl 的列表项目;否则，引入新的（重构）符号Si，并且我们用新的工件newti替换子工件ti其根节点为n ti ¼S i t iV1;.. . ;tiVl;3.如果n的新子工件的列表仅包含一个元素t1，其具有n1/4S1ht1V1;. . ;t1Vli（其中S1a新标记目标工件根的符号。此外，设计师GMWf必须静态地选择负责启动过程的参与者。因此，这位演员将是唯一一位拥有关于新公理AG的书面认可的演员。3.1.2. 伪影投影算法的一些性质它的复杂性。为了投影包含m个节点的工件，这些节点中的每一个都被访问，并且在最坏的情况下，它被重构符号或其子符号替换：这种替换需要重新布置节点所处的树的级别。属于;它导致在一个m-1节点的列表中的探索创建（重新）结构符号）作为根节点，我们在这一个中用子伪影t1V1;. ;t1Vl 的n1。这去除了不重要的（重构）符号S1。● 否则，n被删除，投影的结果（projst）为最坏的情况和原子操作的应用，如置换等。因此二次的O.在最坏的情况下，m2会下降每个子工件的投影的并集：3.1号提案 对于所有GMAWfPW¼。G;LP;L A验证普罗伊斯 ¼ p ð t Þ ¼ Smpðt Þfk ktVi¼1Vi请注意，这里描述的算法适用于所有工件（包括包含芽的工件），因为不需要对芽应用任何特殊处理（锁定或解锁）：它们也必须被擦除或保留在工件中，以确保公理符合其GMWf（t）G），导致单个伪影tV/VPV/tt（通过使用p的伪影的稳定性属性）。9上下文无关文法的产生式是单位产生式，如果它是在形式上A！ B，其中A和B是非终结符。M.M.Z. Ndadji，M.T.Tchendji，C.T.Djamegni等人沙特国王大学学报6110Vð Þ2V公司简介PAV1/4fg.Σ.ΣV.ΣA ¼A.ΣV···.Σ作为它的儿子，一套艺术品t i 1;. ;tinW fV ¼GV;LPk;LAVk，部分证据让注意，只有在这种情况下，投影的艺术-事实t根据视图V产生森林，是当t的根节点与不可见符号X（XRV）相关联时。已知t）G和Wf验证了公理AGofG和AG（因此生成树的唯一性）。由于投影操作保留了乘积的形式因此，可以得出结论，tV¼pVt是伪影。H3.2. GMWf投影算法3.2.1. 该算法该算法的目标是通过根据视图V投影给定的GMWfG^S;P;A来导出局部GMWfGVV;V;V（我们记为GVPVG）。所提出的算法（算法2）生成由G表示的目标伪影集合10然后根据视图对每个目标工件进行投影，然后在去除副本的同时将产生式聚集在所获得的部分副本中。算法2：根据给定视图投影给定GMWf的算法图5示出了局部模型GVEC的研究。 等GVEC 1/2PVECG焦油-从G生成的伪影（图5（b））被投影以获得视图EC（图5（c））。从由此获得的局部目标伪影，产生搜索的GMWf（图13）。 5（d））。这里给出的GMWf投影算法只适用于不允许递归符号的[11]因此，我们假设：对于本文中提出的执行模型，被操纵的GMAWfP是那些GMWf不包含递归符号的GMWf（非递归GMWf假设）。有了这个假设，就不再可能表达流程任务之间的迭代路由（在一般情况下）;除非预先知道最大3.2.2. GMWf投影算法它的复杂性。在投影给定GMWf时，并不总是需要生成目标伪影集，因为它们是已知的，并且已由设计人员根据LSAWfP设计方法（参见第2.2.1节）生成为了投影用m个目标工件产生的GMWf，工件被投影，并且从所产生的工件中收集新的产品;对于给定的工件，该产品收集在线性时间内完成。因此，其目标伪影各自1. 首先，需要生成由G表示的所有目标伪影（参见下面的注释（1））;因此，我们得到一组艺术Gt1;. ;tn;2. 然后，每个目标伪影必须根据V进行投影。因此，我们得到一组ArtsGV1;...... ;tVm（m6n，因为可能存在重复;在这种情况下，只保留一个副本）工件部分副本;3. 然后，收集出现在艺术GV的伪影中的不同（重新）结构化符号，确保去除重复（参见下面的注释（2））并相应地更新最多有n个 节点，在立方时间内完成。O. 2分钟。提案3.2. 对于所有GMAWfPWfG;LPk;L Ak为了验证公理的可见性和GMWf假设的非递归性，其GMWf G ^S; P ; A的投影根据给定的视图V，是GMAWf P W f V的GMWf G V ^P V ^G ^，验证GMWf的公理可见性和非递归性的假设（通过使用P的GMWf的稳定性）。艺术品和布景艺术因此，我们得到一个集合S VStruc 的证据让¼PGMAWfP是一个新GMAWfP的GMWfV符号和最后一套艺术GV 1/4。tV1;. ; tVl（l 6 m）的。Σ符合检索的GMWfGV。所以我们称之为视图的局部目标伪影;4. 在这个阶段，是时候收集为视图V构建每个本地目标工件的所有产品了。我们得到一个不同产生式的集合PV所搜索的本地GMWfGV VVV;PV;AV V V，例如：a. 其符号集为SV ¼V[SVStruc;b. 它的生成集是PV;c. 它的公理在V注（1）：生成由GMWf因此，我们只需使用产品集来GMWf的稳定性和非递归性 由于Wf/G; LPk; L Ak验证了GMWf假设的非递归性，因此目标伪影的集合（artsG/ft1;.. ;tng），它表示的是有限的，因此可以完全枚举。进一步知道Wf验证了公理可 见 性假 设 ，它是推 导的的设 为GV¼tV1¼pVt1;. ;tVn<$pVtn是有限的，并且每个工件tVi的根节点与公理AG2A相关联（参见命题3.1）。GV是从集合艺术GV建立的，它的公理AV ¼A是所有演员都能看到，它的作品只有两种形式为GMWf保留此外，每个新的（重新）结构化符号（S2 S V））仅创建和使用一次，以替换生成具有公理AG2A中的一个公理的伪像的集合，如root.事实上，对于每个公理AG，应该考虑每个AG-产生式P<$AG;X1···X n n n引起伪像结构的在投影艺术品G.因此，新的符号不是递归的。通过在L A中用V[S V]替换视图V，得到新的集合L Aft1t mg，例如：每个t i的根节点标记为A和GVk;......的人。 ;.新GMAWfP的认证.电子验证生成的工件集的笛卡尔积，将每个符号X1;Xn视为根节点。注（2）：在这种情况下，如果对于它们在不同伪影的节点中的所有外观，artsG，它们诱导相同的局部调度。10此生成是必要的，因为每个对等体仅使用的假设公理的可见性和的非递归性GMWf. H3.3号提案对于所有的GMAWfPWf^G;LPk;LAk，证明了公理的可见性和GMWf假设的非递归性，符合GMWf G的伪影t在给定视图V上的投影是符合G的投影的伪影根据V8t;t）G）pVt）PVG。因此，GMWfG并不拥有其所有目标伪影，即使设计师使用这些工件产生了G[11]只有在这种情况下，所有的目标工件才能被枚举。藏物这些是唯一一个W fV ¼GV;LPk;LAVk它验证了公理的视觉假设VM.M.Z. Ndadji，M.T.Tchendji，C.T.Djamegni等人沙特国王大学学报6111.Σ2AVVV由于iVG.ΣVGVΣΣ.ΣVVG图五. 根据给定视图的GMWf投影示例。证据已知所考虑的GMAWf PWf 1/4G;LPk;LAk验证了公理G是一目标伪影8t; t）G（）t 2 artsG（）。因此，考虑到给定的工件t使得t符合G（t）G），则知道它是目标对象，事实（t2artsG）及其根据给定视图V的投影产生单个伪影tV¼pVt（参见“公理AGofG）。由于t是目标伪影，因此其投影tV（通过对一些潜在（重构）符号的重命名）是已经通过应用算法2中描述的投影原理生成了GV^PV^GV的伪影的集合艺术GV的一部分因此，在构造tV时所涉及的产生式都包括在GMWfGVVVV G的产生式集合中。由于GV的公理集是AV < $A，因此可以推导出AG2 AV和con-包括tV）GV。H3.3. 扩展剪枝算法3.3.1. 该算法考虑一个在执行t下的（全局）工件，并且tV^pV^t将其部分副本复制到视图为V的参与者Ai的站点上。考虑部分复制品t主要是通过开发tVA贡献的一些解锁芽而获得的。膨胀问题在于找到在执行tf下的（全局）工件，其集成了t和tV的节点。为了解决t和tV符合两个不同模型（G和GV<$PV <$G）的困难，我们执行三路合并（Mens，2002）。 我们使用（全局）目标伪影tg合并伪影t和tV，使得：(a) t是tg的前缀（t6tg）(b) t_maj是根据下式的t的部分副本的前缀.t maj6p. t提案3.4. 考虑一个GMAWfPWf 1/4G;LPk;L Ak，验证公理的可见性和非递归性假设。对于所有的艺术-事实tV符合PVG，存在至少一个符合G的伪影t， 使得tVPV t8tV; tV）PVG9 t; t）GandtVPV t。证据利用命题3.2该算法分两步进行3.3.2. 步骤1合并指南的搜索是通过（算法3）生成由G表示的目标伪影集合，然后对其进行过滤来完成的。设置为只保留那些以t为前缀的字符串（参见定义并且t_maj是它们根据视图V的投影。VGVV验证公理假设，是一个GMWf验证相同的假设。On this算法3：搜索合并指南根据，并使用类似的推理，用来证明命题，1. 首先，我们要制作布景¼ ft ;......的人。;tgof位置3.3，已确定符合以下是其目标伪影之一（视图V的局部目标伪影）：由G表示的目标伪影;G1ne，Vt 2 arts. 提到投影过程，2. 然后，我们必须过滤这