基于直方图的图的缩小：语法和语义问题

网址：http://www.elsevier.nl/locate/entcs/volume61.html11页基于直方图的图的缩小：语法和语义问题斯图尔特·安德森3约翰·波沃1;4 andKonsta ntinosTourlas2; 5爱丁堡大学信息学系，爱丁堡EH9 3JZ，英国摘要自Statecharts发明以来，基于Harel的分层图或higraph概念的计算系统表示已经变得流行这样的分层表示支持一个有用的过滤操作，称为“缩小”，这是用来管理的详细程度呈现给用户设计或推理有关的大型和复杂的系统。在（轻量级）范畴理论的框架下，我们开发了数学的缩小与松散的边缘higraphs，形式化的过渡语义，这样的higraphs和进行分析的效果缩小的操作上的语义解释，所需的合理性的推理参数取决于缩小的步骤。1引言近年来，在计算系统的规范、建模和编程中，图形符号迅速流行。其中最值得注意的是Statecharts[3]，一种用于对反应式系统进行建模的符号，以及统一建模语言（UML）[9，10]，一种用于基于对象建模的图形符号家族。随着图形语言在计算和软件工程中的普及，支持最佳实践的需求也越来越大，因为它需要一个合理的理论来解释所涉及的大量语法、语义和语用问题图形符号在设计、建模和推理中的有效性的关键是它们通常支持的广泛的操作尤其是-1 这项工作是在EPSRC赠款GR/M56333和英国文化委员会赠款以及STA日本COE预算的支持下完成的。2 非常感谢您对EPSRC赠款GR/N12480和STA日本COE预算的支持。3 电子邮件地址：soa@dcs.ed.ac.uk4 电子邮件地址：ajp@dcs.ed.ac.uk5 电子邮件地址：kxt@dcs.ed.ac.ukc 2002年由Elsevier Science B出版。诉 在CC BY-NC-ND许可下开放访问。2通常，表示现实的复杂系统的图的可用性关键取决于一个人执行重新组织，抽象和过滤图中存在的信息的操作的能力[8]。在系统设计和分析中，我们都希望控制细节的层次。这通常是通过将某个子系统“分块”并将其表示为单个对象来完成的。例如，图1显示了连续的图的“分块”。其他这样的复杂性管理”操作更类似于“过滤”，通过应用一些消除标准来均匀地消除图的一部分中的Fig. 1. 图上的增量分块一个中心问题涉及图上的这种复杂性管理操作的语义导入。这是因为执行这种操作的目的是从系统的表示中消除一些被认为与手头的任务（可以是设计或推理任务）无关的细节，从而简化任务。因此，如果简单表示上的任务的完成意味着关于由原始图表示的系统的任何事情，则将简化图的语义与原始图的语义精确地关联起来是极其重要的本 文 提 出 了 一 个 框 架 的 语 法 和 语 义 的 这 样 一 个 ltering 操 作 的higraphs[4，5]扩展与松散连接的边缘。Higraphs（“hierarchical graphs”的缩写）本身就是图的简单扩展，它允许将节点包含在其他节点中，从而在节点和边之间形成“深度”层次结构。直方图是流行的Statecharts和UML状态图的基础，通常被解释为复杂转换系统的紧凑和经济的表示。我们研究的过滤操作，由Harel在[4]中以缩小的名义简要介绍并激发，通过消除层次结构中某个级别以下的细节来利用深度。第2节介绍了双图的结构（静态）和它们作为状态转换系统的最常见的计算解释（动态）。在第3节中，我们回顾了在[12]中广泛研究的最简单的higraphs缩小形式，并总结了[1]中的详细分析，指出其不足之处wrt。动态和需要松散的连接边缘。3BECDF一图二. 一个简单的higraph后者在第4节中正式介绍，在第5节中，我们定义了一个更精确的概念，即在存在这种边缘的情况下缩小。我们的主要结果扩展了[12，1]中的工作，将缩小捕获为由一对伴随函子描述的重写具有松散连接边的双重图的动力学是第6节的主题，其中游程的概念从普通（或“at”）转移系统扩展到我们的双重图。最后，我们提供了一个分析所产生的问题，在建立一个基于higraph的系统的动态之间的关系，其缩小表示的动态。2希格斯特Histraphs最初由Harel[4，5]开发，作为Statecharts[3]的基础，是图形（“视觉”）对象，通过允许节点之间的空间包含来扩展图形。图2示出了由六个节点和四条边组成的简单higraph的图形表示，其中标记为B、C和D的节点在空间上包含在标记为A.因此，这是常见的，我们以后将坚持公约，呼吁higraph斑点的节点，作为它们作为平面的非空区域的图形表示的指示。如果一个blob中不包含其他blob，则该blob被称为原子blob。空间包含的特征通常被称为深度，导致在Harel的\equation”中表达higraphs与图的关系：higraphs = graphs + depth6.higraphs的主要应用是复杂状态转换系统的规范化和可视化，主要体现在Statecharts中，最近，在UML的状态图中[9]。在这样的应用中，深度既被用作一种概念性的手段，将整个系统分解为有意义的子系统，又被用作中断的一种经济有效的表示。根据图2中的示例higraph，边缘发出-[6]Higraph是Harel创造的一个术语，是层次图的缩写，但经常被广泛使用，包括几个变体。这里所采取的观点是，深度是最有区别的，最重要的特征。哈雷尔的原始定义包括一个额外的功能，他所谓的正交性，这是不处理这里。这是我们的信念，支持本文件的范围之外的初步结果，正交性，至少在数学上，最好被视为一个扩展的基本，\深度只有\”higraphs考虑这里。4ABCDDC一B从二进制大对象A开始可以被认为是中断包括状态（即原子二进制大对象）B、C和D的子系统的操作的更高级转换。因此，当应用于多个级别时，深度通过大幅减少指定状态之间的过渡关系所需的边的数量来促进大型系统例如，higraph简要地表示以下过渡系统：B acdD dC一B读 者 应 该 注 意 到 ， higraphs 的 转 换 解 释 比 Statecharts 更 一 般 在Statecharts中，存在一个工具，根据我们上面的例子，它允许将B或C注释为A中的默认状态。这样的注释迫使从D到A的箭头是从D到A中的默认状态的转换，从而消除了非确定性选择。虽然这样的设备可以很容易地添加到higraphs，我们选择不这样做，在本文件的一般性和简单的说明的原因图也被用于其他建模符号的扩展，例如数据库分析和设计中流行的关系图（ER）[4，5]。在该上下文中，blob表示集合（或某些特定类型的记录的“表”），而包含被直接解释为集合包含。2.1Higraphs，正式的我们对higraph的定义是基于Harel的[4]，但使用偏序集（即偏序集）来捕捉深度的概念，并将其扩展到边缘：定义2.1双图是一个5元组（B;B; E;E; s; t），其中B和E分别是斑点和边的集合，B是B上的偏序，E是E上的偏序，且s;t：E！B是单调函数，对于每个边e2E，给出其源斑点s（e）和目标斑点t（e）。2例2.2图2可以看作是一个高图的图示，其中：斑点：f A; B; C; D; E; F g，其中B; C; D

下载后可阅读完整内容，剩余1页未读，立即下载