Formal Verification of Object-Oriented Graph Grammars Specifications

Concurrent object-oriented systems are ubiquitous due to the importance of networks and the current demands for modular, reusable, and easy to develop software. However, checking the correctness of such systems is a hard task, mainly due to concurrency and inheritance aspects. In this paper we present an approach to the verification of concurrent object-oriented systems. We use graph grammars equipped with object oriented features (including inheritance and polymorphism) as the specification formalism, and define a translation from such specifications to Promela, the input language of the SPIN model checker.     

面向关系型数据与知识图谱的数据集成技术综述

目前,各个国家和地区均已将大数据视为重要的战略资源.然而,大数据时代普遍存在数据流通困难、数据监管不足等问题,致使数据孤岛现象严重,数据质量低下,数据要素潜能难以释放.这驱使研究人员探索数据集成技术,以打破数据壁垒、实现信息共享、提升数据质量,进而激活数据要素潜能.关系型数据和知识图谱作为两种至关重要的数据组织与存储形式,在现实生活中应用广泛.为此,聚焦关系型数据和知识图谱,归纳总结并分析实体解析、数据融合、数据清洗3方面的数据集成关键技术,最后展望未来研究方向与趋势.     

A Query Language for XML Based on Graph Grammars

In this paper we present a graphical query language for XML. The language, based on a simple form of graph grammars, permits us to extract data and reorganize information in a new structure. As with most of the current query languages for XML, queries consist of two parts: one extracting a subgraph and one constructing the output graph. The semantics of queries is given in terms of graph grammars. The use of graph grammars makes it possible to define, in a simple way, the structural properties of both the subgraph that has to be extracted and the graph that has to be constructed. We provide an example-driven comparison of our language w.r.t. other XML query languages, and show the effectiveness and simplicity of our approach.     

基于约束依赖图的并发程序模型检测工具

模型检测是一种基于状态空间搜索的自动化验证方法,可以有效地提升程序的质量.然而,由于并发程序中线程调度的不确定性以及数据同步的复杂性,对该类程序验证时存在更为严重的状态空间爆炸问题.目前,大多采用基于独立性分析的偏序约简技术缩小并发程序探索空间.针对粗糙的独立性分析会显著增加需探索的等价类路径问题,开发了一款可细化线程迁移依赖性分析的并发程序模型检测工具CDG4CPV.首先,构造了待验证可达性性质对应的规约自动机;随后,根据线程迁移边的类型和共享变量访问信息构建约束依赖图;最后,利用约束依赖图剪裁控制流图在展开过程中的独立可执行分支.在SV-COMP 2022竞赛的并发程序数据集上进行了对比实验,并对工具的效率进行比较分析.实验结果表明,该工具可以有效地提升并发程序模型检测的效率.特别是,与基于BDD的程序分析算法相比,该工具可使探索状态数目平均减少91.38%,使时间和空间开销分别平均降低86.25%和69.80%.     

工具集成的框架及工具间的关系

本文主要探讨了工具集成的框架，集成所涉及的数据集成、控制集成、过程集成，以及工具间的关系，工具间的关系主要讨论工具家族中的成员关系准则，构造良好的工具配置，工具的向上兼容关系，以及工具修订的影响范围。     

图嵌入模型综述

图分析用于深入挖掘图数据的内在特征,然而图作为非欧几里德数据,传统的数据分析方法普遍存在较高的计算量和空间开销。图嵌入是一种解决图分析问题的有效方法,其将原始图数据转换到低维空间并保留关键信息,从而提升节点分类、链接预测、节点聚类等下游任务的性能。与以往的研究不同,同时对静态图和动态图嵌入文献进行全面回顾,提出一种静态图嵌入和动态图嵌入通用分类方法,即基于矩阵分解的图嵌入、基于随机游走的图嵌入、基于自编码器的图嵌入、基于图神经网络(GNN)的图嵌入和基于其他方法的图嵌入。其次,对静态图和动态图方法的理论相关性进行分析,对模型核心策略、下游任务和数据集进行全面总结。最后,提出了四个图嵌入的潜在研究方向。     

含假结RNA二级结构类的图语法

用最小自由能法预测RNA二级结构是NP困难问题,其根本原因是假结的存在。近几年的预测算法都针具有一定结构特征的假结寻找多项式时间算法进行预测。论文针对RNA二级结构图提出一种图语法,该语法由初始结构图集和重写规则集构成,用重写规则在初始结构图上的不断重写得到的结构图都是该语法的语言。分析了5个主流RNA二级结构预测算法的目标集,给出它们的图语法,使得目标集的结构特征一目了然,目标集间的真包含关系也通过图语法直观地体现出来。     

动态图划分算法研究综述

图划分是大规模分布式图处理的首要工作,对图应用的存储、查询、处理和挖掘起基础支撑作用.随着图数据规模的不断扩大,真实世界中的图表现出动态性.如何对动态图进行划分,已成为目前图划分研究的热点问题.从不同动态图划分算法的关注点和特点出发,系统性地介绍当前可用于解决动态图划分问题的各类算法,包括流式图划分算法、增量式图划分算法和图重划分算法.首先介绍图划分的3种不同的划分策略及问题定义、图的两种不同的动态性来源以及动态图划分问题;然后介绍3种不同的流式图划分算法,包括基于Hash的划分算法、基于邻居分布的划分算法以及基于流的优化划分算法;其次介绍单元素增量式划分和批量增量式划分这两种不同的增量式图划分算法;再次,分别介绍针对图结构动态的重划分算法和针对图计算动态的重划分算法;最后,在对已有方法分析和比较的基础上,总结目前动态图划分面临的主要挑战,提出相应的研究问题.     

基于扩展对象关系图的集成测试研究

测试顺序是面向对象软件集成测试中的一个重要问题。本文提出使用扩展对象关系图作为测试模型研究面向对象软件集成测试顺序问题,并给出计算测试顺序的算法以及设计测试用例的策略。     

工具服务化集成中数据交互方式设计

针对当前工具服务化集成中数据交互普遍存在的语法异构和语义异构问题,本文设计了一种基于JSON格式的语法定义形式和基于通用词表的语义异构处理方法的数据交互方式,并对其实现方法和技术进行了详细的论述.最后,在一种软件开发工具服务化集成的实际案例中进行了实验,对所提出的数据交互方式进行了实现并对其有效性进行了验证.实验结果表明,所设计的数据交互方式较好地解决了上述两个问题,为工具集成提供了良好的数据交互基础.     

图计算加速架构综述

在大数据时代,图被用于各种领域表示具有复杂联系的数据.图计算应用被广泛用于各种领域,以挖掘图数据中潜在的价值.图计算应用特有的不规则执行行为,引发了不规则负载、密集读改写更新操作、不规则访存和不规则通信等挑战.现有通用架构无法有效地应对上述挑战.为了克服加速图计算应用面临的挑战,大量的图计算硬件加速架构设计被提出.它们为图计算应用定制了专用的计算流水线、访存子系统、存储子系统和通信子系统.得益于这些定制的硬件设计,图计算加速架构相比于传统的通用处理器架构,在性能和能效上均取得了显著的提升.为了让相关的研究学者深入了解图计算硬件加速架构,首先基于计算机的金字塔组织结构,从上到下对现有工作进行分类和总结,并以多个完整架构实例分析应用于不同层次的优化技术之间的关系.接着以图神经网络加速架构的具体案例讨论新兴图计算应用的加速架构设计.最后对该领域的前沿研究方向进行了总结,并放眼于未来探讨图计算加速架构的发展趋势.     

一种基于工具总线的CASE集成模型

简要分析了当前CASE环境的集成机制,并给出了一种基于工具总线的工具集成机制的理论架构以及实现。该机制引入了工具适配器对工具总线的底层机制进行封装,满足了系统对集成的应用工具的位置无关性的要求。     

知识图谱划分算法研究综述

知识图谱是人工智能的重要基石,因其包含丰富的图结构和属性信息而受到广泛关注.知识图谱可以精确语义描述现实世界中的各种实体及其联系,其中顶点表示实体,边表示实体间的联系.知识图谱划分是大规模知识图谱分布式处理的首要工作,对知识图谱分布式存储、查询、推理和挖掘起基础支撑作用.随着知识图谱数据规模及分布式处理需求的不断增长,...     

Small-Scale XMI Programming: A Revolution in UML Tool Use?

The main motivation for the development of the OMG's XML Metadata Interchange Format (XMI) was the need to have a standard way for UML tools to interchange UML models. However, the fact that UML models, saved as XML documents, are now accessible to standard XML tools, opens up new possibilities to which less attention has so far been paid. This paper discusses how XMI can be exploited for performing model analysis and housekeeping tasks and for the integration of third party or in-house tools. With the help of examples we focus on what can be achieved with small-scale XMI programming by a single developer in hours rather than days. We suggest that this new capability may have important and positive implications for the future of UML modelling using tools.     

知识图谱数据管理研究综述

知识图谱是人工智能的重要基石.各领域大规模知识图谱的构建和发布对知识图谱数据管理提出了新的挑战.以数据模型的结构和操作要素为主线,对目前的知识图谱数据管理理论、方法、技术与系统进行研究综述.首先,介绍知识图谱数据模型,包括RDF图模型和属性图模型,介绍5种知识图谱查询语言,包括SPARQL、Cypher、Gremlin、PGQL和G-CORE;然后,介绍知识图谱存储管理方案,包括基于关系的知识图谱存储管理和原生知识图谱存储管理;其次,探讨知识图谱上的图模式匹配、导航式和分析型3种查询操作.同时,介绍主流的知识图谱数据库管理系统,包括RDF三元组库和原生图数据库,描述目前面向知识图谱的分布式系统与框架,给出知识图谱评测基准.最后,展望知识图谱数据管理的未来研究方向.     

Behavioral Refinement of Graph Transformation-Based Models

Model-driven software engineering requires the refinement of abstract models into more concrete, platform-specific ones. To create and verify such refinements, behavioral models capturing recon- figuration or communication scenarios are presented as instances of a dynamic meta-model, i.e., a typed graph transformation system specifying the concepts and basic operations scenarios may be composed of. Possible refinement relations between models can now be described based on the corresponding meta-models.In contrast to previous approaches, refinement relations on graph transformation systems are not defined as fixed syntactic mappings between abstract transformation rules and, e.g., concrete rule expressions, but allow for a more loose, semantically defined relation between the transformation systems, resulting in a more flexible notion of refinement.     

面向链接预测的知识图谱嵌入研究综述

知识图谱在人工智能领域有着广泛的应用,如信息检索、自然语言处理、推荐系统等。然而,知识图谱的开放性往往意味着它们是不完备的,具有自身的缺陷。鉴于此,需建立更完整的知识图谱,以提高知识图谱的实际利用率。利用链接预测通过已有关系来推测新的关系,从而实现大规模知识库的补全。通过比较基于翻译模型的知识图谱链接预测模型,从常用数据集与评价指标、翻译模型、采样方法等方面分析知识图谱链接预测模型的框架,并对基于知识图谱的链接预测模型进行了综述。     

A Prolog Framework for the Rapid Prototyping of Language Processors with Attribute Grammars

In this paper, we describe PAG (Prototyping with Attribute Grammars), a framework for building Prolog prototypes from specifications based on attribute grammars, which we have developed for supporting rapid prototyping activities in an introductory course on language processors. This framework works for general non-circular attribute grammars with arbitrary underlying context-free grammars, includes a specification language embedded in Prolog that strongly resembles the attribute grammar notations explained in the course cited, and lets students produce comprehensible prototypes from their specifications in a straightforward way.     

基于STEP的CAD/CAPP集成工具的研究

长期以来,ＣＡＤ／ＣＡＰＰ信息集成一直是ＣＩＭＳ系统的难点之一,且没有得到较好的解决。ＳＴＥＰ标准的发展和应用,使其成为ＣＡＤ／ＣＡＰＰ／ＣＡＭ系统信息集成的基础。随着越来越多的ＣＡＤ系统支持ＳＴＥＰ标准,开发基于ＳＴＥＰ的ＣＡＤ／ＣＡＰＰ集成工具成为当务之急。     

Factbase Filtering Issues in an Ontology-Based Reverse Engineering Tool Integration System

The Ontological Adaptive Service-Sharing Integration System (OASIS) facilitates reverse engineering tool interoperability by sharing services among tools that represent software in a conceptually equivalent manner. OASIS uses a domain ontology to record the representational and service-related concepts each tool offers. Specialized adapters use a filtering process to map factbase instances to domain ontology concepts and apply shared services. This paper examines three issues related to the filtering process: representational correspondence, loss of precision and information dilution.