An Improved Approach to Test Diagnosability of Bounded Petri Nets

For bounded Petri nets, Cabasino et al. propose a diagnosability test method that is based on the analysis of a modified basis reachability graph and a basis reachability diagnoser. However, its complexity is exponential in the number of nodes of the basis reachability diagnoser. In order to reduce the complexity of their method, this paper presents a new diagnosability test approach for bounded Petri nets. We present the concept of an extended basis reachability graph and prove that our approach is of polynomial complexity in the number of nodes of extended basis reachability graphs. An example is given to illustrate the application of the presented approach.      

Diagnosability of digital systems structured as minimal quasicomplete 7 × 7 graph

An approach was developed to estimate the values of diagnosability of digital systems with the novel structure of the minimal quasicomplete 7 × 7 graph. The proposed estimates of the values of diagnosability of the digital systems under consideration were established as the result of diagnosis of fault situations in a system of 7 users and 7 switches. Consideration was given to two variants of organization of the components of the analyzed digital system for which different estimates of diagnosability were established.     

A graph-based generic type system for object-oriented programs

We present a graph-basedmodel of a generic type system for an OO language. The type system supports the features of recursive types, generics and interfaces, which are commonly found in modern OO languages such as Java. In the classical graph theory, we define type graphs, instantiation graphs and conjunction graphs that naturally illustrate the relations among types, generics and interfaces within complex OO programs. The model employs a combination of nominal and anonymous nodes to represent respectively types that are identified by names and structures, and defines graph-based relations and operations on types including equivalence, subtyping, conjunction and instantiation. Algorithms based on the graph structures are designed for the implementation of the type system. We believe that this type system is important for the development of a graph-based logical foundation of a formal method for verification of and reasoning about OO programs.     

A hybrid method for finite element ordering

Nodal ordering for the formation of suitable sparsity patterns for stiffness matrices of finite element meshes are often performed using graph theory and algebraic graph theory. In this paper a hybrid method is presented employing the main features of each theory. In this method, vectors containing certain properties of graphs are taken as Ritz vectors, and using methods for constructing a complementary Laplacian, a reduced eigenproblem is formed. The solution of this problem results in coefficients of the Ritz vectors, indicating the significance of each considered vector.The present method uses the global properties of graphs in ordering, and the local properties are incorporated using algebraic graph theory. The main feature of this method is its capability of transforming a general eigenproblem into an efficient approach incorporating graph theory. Examples are included to illustrate the efficiency of the presented method.     

Minimal functional routes in directed graphs with dependent edges

Graphs are mathematical structures used to model a set of objects and the relations between them. One of the basic concepts of graph theory, the path, has wide real‐world applications. In classic graph models, edges ending at a node are assumed to be independent. However, many real graphs/networks can only be correctly described by considering a dependency among nodes or edges. Paths in such graphs may not be functional if the conditional dependency is ignored. In this study, we investigate the routing problem in directed graphs with dependent edges represented by general graph models as alternatives to hypergraphs. We define a minimal functional route (MFR) as a minimal set of nodes and edges that can independently perform information transfer between two given nodes, and formulate the determination of MFRs as a graph search problem. A depth‐first‐search (DFS) top‐down algorithm, an iterative integer linear programming (ILP) bottom‐up algorithm, and a subgraph‐growing bottom‐up algorithm are devised subsequently to solve this problem. Numerical experiments verify the effectiveness of the algorithms. The defined MFR problem and the proposed algorithms are expected to find many practical applications.     

超网络能量研究与应用

图能量是图论研究的重要内容,图能量及其变种已在无向图、有向图、混合图等其他多种类型的图中得到很多成功的应用.超网络是一类较传统意义上的复杂网络更为复杂的网络.大多数图能量均是基于矩阵特征值计算得到的,无法推广应用到超网络中,应用范围受限.基于网络维数的网络能量已先后应用于无向图、有向图等多种类型图的分析研究中,并与无向...     

Binary relations,matrices and inference developments

The relationships among binary relations, directed graphs and boolean matrices are discussed. The development of new relations from given relations is described in terms of boolean matrix operations.The development of new relations from given relations is equivalent to inferring new relationships from the given facts and the operations on these facts. Given a directed graph, one can infer all the facts possible by completing the graph. An alternative method is to store the given facts and upon being queried, one derives the results required.Two algorithms are described which employ matrix operations to make explicit new relationships that are implicit as a result of the given facts and general rules which map sets of relations into new relations. The two algorithms are analyzed in terms of space and time requirements. Comments are made concerning the practicality of the approach.     

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

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

System-level operational diagnosability analysis in quasi real-time fault diagnosis: The probabilistic approach

Fault diagnosis is routinely carried out with the aid of the various data processing methods, yet the relations between the normal state and different faulty states are considered less, which should be the major concern of the diagnosability issue. In this paper the probabilistic derivation of diagnosability is presented for the faults containing uncertainties, and a method for analyzing system-level quasi real-time diagnosability is given. The stochastic characterizations of different fault modes are extracted and a measurement based on the modified distance is established to quantify diagnosability performance. Diagnosability includes detectability and distinguishability, and the two parts are the same in essence that they both identify the distinction of two different states. The operational diagnosability is also addressed in the quasi real-time setting where the system-level diagnosis is carried out with the state data of the critical components. Finally, the method is applied to a single-stage vapor compressor refrigeration cycle system to exemplify how to analyze diagnosability of a system dynamic with the input data from its critical component.     

Knowledge Representation of Software Component Interconnection Information for Large-Scale Software Modifications

Logic can be used to precisely express human thoughts and inferences. In this paper, an approach using first-order logic for knowledge representation of software component interconnection information to facilitate the validity and integrity checking of the interconnection among software components during software development or modification is presented. Directed graphs are first used to model the structure and behavior of a large-scale software system, and a first-order theory of directed graphs (the DG theory) is established. The interconnection behavior among software components in a large-scale software system is a directed graph which is called software component interconnection graph (CIG). The behavior of the CIG is interpreted using the DG theory and translated into logic representation. The translated logic representation is a set of logic clauses and can be considered as a set of axioms. Automated reasoning techniques based on these axioms can be used to perform the validity and integrity checking of software properties in the software development or maintenance phase.     

Synchronization and convergence of linear dynamics in random directed networks

Recently, methods in stochastic control are used to study the synchronization properties of a nonautonomous discrete-time linear system x(k+1)=G(k)x(k) where the matrices G(k) are derived from a random graph process. The purpose of this note is to extend this analysis to directed graphs and more general random graph processes. Rather than using Lyapunov type methods, we use results from the theory of inhomogeneous Markov chains in our analysis. These results have been used successfully in deterministic consensus problems and we show that they are useful for these problems as well. Sufficient conditions are derived that depend on the types of graphs that have nonvanishing probabilities. For instance, if a scrambling graph occurs with nonzero probability, then the system synchronizes.     

Local diagnosability of generic star-pyramid graph

The problem of fault diagnosis in network has been discussed widely. In this paper, we study the local diagnosability of a generic star-pyramid graph. We prove that under the PMC model the local diagnosability of each vertex in a generic star-pyramid graph is equal to its degree and the generic star-pyramid has the strong local diagnosability property. Then we study the local diagnosability of a faulty graph. After showing some properties of the graph, we prove that a generic star-pyramid graph keeps the strong property no matter how many edges are faulty under the condition that each vertex is incident with at least four fault-free edges.     

On the route-oriented method of system diagnostics in digital systems structured as a symmetric bipartite graph

We propose a method for organizing the route-oriented method for diagnostics of digital systems (DS) with the structure of a symmetric bipartite graph. To describe the results of testing individual units, we use the Preparata-Metze-Chien model (PMC). We suppose that the system has a diagnostic monitor that initiates the diagnostic processes. To estimate the value of diagnosability in the analyzed DS, we use the method of potential syndromes. We show that the analyzed DS are no more than 1-diagnosable without repair. For a system including seven processors and seven memory units, we consider an example with an unreliable diagnostics of three faulty components.     

Taxonomy and formal properties of distributed joins

A general framework for studying the properties of joins between fragmented relations is presented. A join between fragmented relations can be performed as a set of partial joins between their fragments and can be represented as a join graph. A taxonomy of join graphs is developed. Rules are given for determining the class of a join graph from the properties of the fragmentation of relations and from semantic knowledge of different types of database dependencies. The fact that a join graph belongs to a given class is relevant for the efficiency of join execution; two typical application areas of these results are the design of distributed databases and the optimization of distributed queries.     

An approach to capturing and reusing tacit design knowledge using relational learning for knowledge graphs

Tacit design knowledge plays an important role in the process of product design and is a valuable knowledge asset for enterprises. In terms of the characteristics of tacit rational design knowledge, this paper puts forward a scientific hypothesis and approach on capturing and reusing tacit rational design knowledge. The presented approach represents the observable design result facts of products using design knowledge graphs. A design issue-solving oriented knowledge graph model is presented, where directed relation edges represent design issues, and nodes stand for design solutions. When a new design solutions requirement needs to be searched, tacit design knowledge can be reused by relational learning for the constructed design knowledge graphs. In relational learning, the design knowledge graph is converted into a three-order tensor, where two modes are solution nodes, and the third mode holds the issue relations. Then, a tensor factorization approach is employed to calculate the latent features between design solutions for an issue relation. As a result, a score vector to represent the existence of issue-solution relations can be obtained. By sorting the scores in descending order, we may select the solution node with the highest score as the design solution to be searched. Finally, a stamping die design case study is provided. The case study shows that the proposed approach is feasible, and effective, and has better flexibility, scalability and efficiency than CBR methods.     

Hierarchical representation of complex systems for supporting human decision making

The work presented in this paper is devoted to intelligent on-line supervision tools. In the proposed approach, the human operator remains in the decision loop, at the highest level, and acts on the process. To help operators make decisions, process knowledge is represented with a model whose complexity can be adapted on line to the operation needs at the request of the operator. The model thus helps to focus only on the phenomena that are relevant at a given time. To give the model explanatory capacity, it is represented as a causal directed graph, and allows the representation of temporal phenomena, which is fundamental for dynamic monitoring. A hierarchical representation of the functional properties of the process is proposed. The conception of a hierarchy of causal models with a top-down analysis is discussed. Path algebra is used to construct a higher-level graph on-line at the request of the operator from the most detailed graph, while conserving the semantics of the latter. No intermediate level is defined a priori; only the highest and lowest level graphs are fixed: the others are constructed dynamically. Finally, a study of how graphs can convey information on the dynamics of the process for approximate temporal reasoning that is largely sufficient for supervision purposes is analyzed. An example of a causal graph hierarchy for a nuclear process illustrates the method. As a final point, the use of such causal graphs in advanced industrial supervision tools is considered.     

Checking p-t diagnosability of a system

In this paper the probabilistic measure of diagnosability, p-t diagnosability, originally proposed in [11], is used to study the diagnosability of digital systems. The system is represented by the graph theoretic model and assuming that failure probability of each unit is a priori known, a new necessary and sufficient condition has been proposed to check the p-t diagnosability of the system.     

基于三维行为关系图的模型一致性检测方法

在业务流程模型的相似性分析过程中,有时会出现环结构。已有的方法一般不考虑环结构,忽略了环结构对模型一致性分析的影响。以Petri网的多重变迁集为基础,提出一种新的一致性度测量方法。首先通过分析5种行为序列关系来刻画Petri网的变迁之间的相互关系,给出了三维行为关系图的概念;然后对Petri网的三维行为关系图间的关系进行研究,提出了基于Petri网的三维行为关系图的一致性检测方法。理论分析和实例测试均表明了该方法的有效性。     

Kronecker product graph matching

In this paper the Interpolator-based Kronecker product graph matching (IBKPGM) algorithm for performing attributed graph matching is presented. The IBKPGM algorithm is based on the Kronecker product graph matching (KPGM) formulation. This new formulation incorporates a general approach to a wide class of graph matching problems based on attributed graphs, allowing the structure of the graphs to be based on multiple sets of attributes. Salient features of the IBKPGM algorithm are that no assumption is made about the adjacency structure of the graphs to be matched, and that the explicit calculation of compatibility values between all vertices of the reference and input graphs as well as between all edges of the reference and input graphs are avoided.