A semantically meaningful characterization of reducible flowchart schemes

A “scalar” flowchart scheme, i.e. one with a single begin “instruction” is reducible iff its underlying flowgraph is reducible in the sense of Cocke and Allen or Hecht and Ullman. We characterize the class of reducible scalar flowchart schemes as the smallest class containing certain members and closed under certain operations (on and to flowchart schemes). These operations are “semantically meaningful’ in the sense tha operations of the same form are meaningful for “the” functions (or partial functions) computed by interpreted flowchart schemes; moreover, the schemes and the functions “are related by a homomorphism.” By appropriately generalizing “flowgraph” to (possibly) several begins (i.e. entries) we obtain a class of reducible “vector” flowchart schemes which can be characterized in a manner analogous to the scalar case but involving simpler more basic operations (which are also semantically meaningful). A significant side effect of this semantic viewpoint is the treatment of multi-exit flowchart schemes on an equal footing with single exit ones.     

Algebraic representation of structured R-programs

Conclusion The algebraic approach to representation of various graph structures and operations on them has been exploited by a number of authors [5, 6]. It should be noted, however, that the previous authors essentially relied on the notion of abstract computer memory, and the main focus was on the analysis of the informal meaning of the algorithms. The distinctive feature of our study is the construction of an algebra that depends only on the topological structure of the R-graphs, i.e., structure invariant under various arc loadings. The existence of this algebra leads to a useful representation of R-graphs, and the operations introduced in this paper may be used as technological operations for various programming transformations — optimization, verification, and debugging of graphic programs. Moreover, by associating a type with each R-graph, we can efficiently store R-graphs in computer memory in the form of linear lists, which simplifies the development of system programs of R-graph manipulation. Note, however, that effective use of the algebraic approach in R-technology requires a more detailed study of the R-algebra, especially in the direction of identical transformations.Translated from Kibernetika, No. 5, pp. 14–21, September–October, 1988.     

Algebraic solutions to recursion schemes

The main problem in recursive scheme theory is determining how to solve a scheme and express its solution. Up to now this was always achieved by adding restrictive hypotheses either on the schemes themselves, or on the domains where they take their values, e.g., assuming the domains have a metric or an order structure and are complete with respect to this structure, or are iterative. Here we develop a strictly algebraic theory of recursion schemes with second-order substitutions. As it is strictly algebraic, the theory applies not only to all recursion schemes on trees, but also to recursion schemes on arbitrary algebras presented in the usual way by generators and relations. In particular, this gives a semantics for nondeterminism and for process algebras.     

A graph theoretic approach to simulation and classification

A new class of discrete random fields designed for quick simulation and covariance inference under inhomogeneous conditions is introduced and studied. Simulation of these correlated fields can be done in a single pass instead of relying on multi-pass convergent methods like the Gibbs Sampler or other Markov chain Monte Carlo algorithms. The fields are constructed directly from an undirected graph with specified marginal probability mass functions and covariances between nearby vertices in a manner that makes simulation quite feasible yet maintains the desired properties. Special cases of these correlated fields have been deployed successfully in data authentication, object detection and CAPTCHA¹ generation. Further applications in maximum likelihood estimation and classification such as optical character recognition are now given within.     

String and graph grammar characterizations of bounded regular languages

Two grammatical characterizations of the bounded regular languages are presented: one in terms of graph grammars, the other using string grammars. First it is shown that a class of state graphs recognizing the bounded regular languages can be generated by a particular second-order contextfree graph grammar. Next we call uniquely recursive a right-linear (string) grammar having at most one right-recursive production for each of its nonterminals. It is then established that the class of languages generated by uniquely recursive, sequential right-linear grammars is exactly the bounded regular languages. Some comments on the relationship between string and graph grammars are made.     

Lukasiewicz逻辑值上下文无关语言的代数刻画

提出了基于Lukasiewicz逻辑的下推自动机（l-VPDA）的概念,从代数角度研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用模糊状态构造,证明了任意以终状态方式接受模糊语言的l-VPDA与状态转移为经典函数且具有l值模糊终状态的l-VPDA间的相互等价性;并证明任意以空栈方式接受模糊语言的l-VPDA与状态转移除一步转移为模糊的以外,其余都是经典函数的l-VPDA是相互等价的;详细研究了l-值模糊上下文无关语言的代数和层次刻画,以及对于正则运算的封闭性。     

一种基于图论的计算蛋白质数据库代表序列的算法

许多生物序列数据库中都含有大量的冗余序列,这些冗余序列通常不利于对数据库的统计分析和处理,而且它们要占用更多的计算机存储和处理资源.针对这个问题,本文中我们设计了一种去除蛋白质冗余序列的算法.该算法基于图论最大独立集的概念来生成非冗余序列集合,对目前存在的不少蛋白质去冗余程序所采用的由Hobohm和Sander最早设计的一种首先将序列分成若干簇然后取出代表序列的算法进行了改进,使得生成了更多的非冗余代表序列集合,避免了一些非冗余的序列也被去除.我们开发出了实现该算法的程序FastCluster,可以用来去除蛋白质数据库中的冗余序列.     

Algebraic determination of circuits in a directed graph

An efficient method has been proposed in this paper to generate all directed circuits in a given arbitrary directed graph. A new concept, the reachability equation of a vertex, has been introduced to tackle the problem in a purely algebraic way.     

A study of graph partitioning schemes for parallel graph community detection

This paper presents a study of graph partitioning schemes for parallel graph community detection on distributed memory machines. We investigate the relationship between graph structure and parallel clustering effectiveness, and develop a heuristic partitioning algorithm suitable for modularity-based algorithms. We demonstrate the accuracy and scalability of our approach using several real-world large graph datasets compared with state-of-the-art parallel algorithms on the Cray XK7 supercomputer at Oak Ridge National Laboratory. Given the ubiquitous graph model, we expect this high-performance solution will help lead to new insights in numerous fields.     

A graph theoretic approach to multivariable control system design

A graph theoretic approach is described for the design of multivariable control for large systems as an alternative to geometric methods. An example is given f⊙r a distillation column to demonstrate the technique, with a particular reference to aspects of disturbance rejection and the possibilities for pole assignment.     

Distance metric learning for graph structured data

Machine Learning - Graphs are versatile tools for representing structured data. As a result, a variety of machine learning methods have been studied for graph data analysis. Although many such...     

Segmentation of color images using multiscale clustering and graph theoretic region synthesis

A multiresolution color image segmentation approach is presented that incorporates the main principles of region-based segmentation and cluster-analysis approaches. The contribution of This work may be divided into two parts. In the first part, a multiscale dissimilarity measure is proposed that makes use of a feature transformation operation to measure the interregion relations with respect to their proximity to the main clusters of the image. As a part of this process, an original approach is also presented to generate a multiscale representation of the image information using nonparametric clustering. In the second part, a graph theoretic algorithm is proposed to synthesize regions and produce the final segmentation results. The latter algorithm emerged from a brief analysis of fuzzy similarity relations in the context of clustering algorithms. This analysis indicates that the segmentation methods in general may be formulated sufficiently and concisely by means of similarity relations theory. The proposed scheme produces satisfying results and its efficiency is indicated by comparing it with: 1) the single scale version of dissimilarity measure and 2) several earlier graph theoretic merging approaches proposed in the literature. Finally, the multiscale processing and region-synthesis properties validate our method for applications, such as object recognition, image retrieval, and emulation of human visual perception.     

Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width

In a previous paper (J. Comput. System Sci. 64 (2002) 519), the authors introduced the notion of hypertree decomposition and the corresponding concept of hypertree width and showed that the conjunctive queries whose hypergraphs have bounded hypertree width can be evaluated in polynomial time. Bounded hypertree width generalizes the notions of acyclicity and bounded treewidth and corresponds to larger classes of tractable queries. In the present paper, we provide natural characterizations of hypergraphs and queries having bounded hypertree width in terms of game-theory and logic. First we define the Robber and Marshals game, and prove that a hypergraph H has hypertree width at most k if and only if k marshals have a winning strategy on H, allowing them to trap a robber who moves along the hyperedges. This game is akin the well-known Robber and Cops game (which characterizes bounded treewidth), except that marshals are more powerful than cops: They can control entire hyperedges instead of just vertices. Kolaitis and Vardi (J. Comput. System Sci. 61 (2000) 302) recently gave an elegant characterization of the conjunctive queries having treewidth <k in terms of the k-variable fragment of a certain logic L (=existential-conjunctive fragment of positive FO). We use the Robber and Marshals game to derive a surprisingly simple and equally elegant characterization of the class HW[k] of queries of hypertree width at most k in terms of guarded logic. In particular, we show that HW[k]=GF_k(L), where GF_k(L) denotes the k-guarded fragment of L. In this fragment, conjunctions of k atoms rather than just single atoms are allowed to act as guards. Note that, for the particular case k=1, our results provide new characterizations of the class of acyclic queries. We extend the notion of bounded hypertree width to nonrecursive stratified Datalog and show that the k-guarded fragment GF_k(FO) of first-order logic has the same expressive power as nonrecursive stratified Datalog of hypertree width at most k.     

Fault diagnosis in dynamical systems: a graph theoretic approach

Fault diagnosis is a vital aspect in the design of operational control systems for large-scale systems with stringent requirements on safety and reliability. In this paper, we develop graph representations for the failure propagation in large-scale systems. Using this model, we present efficient algorithms for failure source identification for single and multiple faults, for diagnosis of faulty alarms, and for forewarning and fault simulation. All these algorithms are analysed for their worst-case complexities. The treatment is algorithmic and graph theoretic and no reference is made to the underlying physical systems.     

Sub-optimal solutions to track detection problem using graph theoretic concepts

This paper demonstrates how the problem of tracking targets, which appear as either straight or curved lines in two-dimensional display images (or data images) can be formulated in terms of a directed weighted graph model and how dynamic programming techniques can be efficiently applied to reach an optimal or sub-optimal solution. In general, track detection algorithms providing optimal solutions have good detective ability, but most of them suffer from the inability to detect discontinuous lines or to resolve efficiently pairs of crossing lines. A sub-optimal solution is provided that efficiently overcomes these weaknesses. We focus on modeling the track detection problem in terms of a graph, formulating fast sequential/parallel sub-optimal track detection algorithms and testing them on simulated data in order to show their detective ability. Moreover, we specify the conditions under which sub-optimal algorithms can perform at least as well as their corresponding optimal algorithms. This is significant for the track detection problem where fast, accurate and real-time detection is considered a necessity.     

VLSI-efficient schemes for high-speed construction of tangent graph

Tangent graph based data structure has been readily used in motion planning for mobile robots and robot manipulators. The complexity of the tangent graph grows exponentially as the robot's configuration space increases in dimension. The ability to construct larger number of tangents at high speed thus becomes crucial to facilitate dynamic motion planning where on-line avoidance is necessary. In this paper, we present efficient schemes for construction of tangent graphs for an environment consisting of both non-convex and convex obstacles. The proposed technique for tangent graph construction is based on a gradient computation approach that encompasses binary search, logarithmic approximation, and half-plane computation modules. The modules were ported to Very Large Scale Integration (VLSI) using commercial tools. Synthesis results show that each module has a latency of only 7.2 ns and a total chip area of about 7K NAND gates, thus demonstrating that the proposed techniques are highly appropriate for tangent graph computations in real-time applications.     

A simple graph theoretic characterization of reachability for positive linear systems

In this paper we consider discrete-time linear positive systems, that is systems defined by a pair (A,B) of non-negative matrices. We study the reachability of such systems which in this case amounts to the freedom of steering the state in the positive orthant by using non-negative control sequences. This problem was solved recently [Canonical forms for positive discrete-time linear control systems, Linear Algebra Appl., 310 (2000) 49]. However we derive here necessary and sufficient conditions for reachability in a simpler and more compact form. These conditions are expressed in terms of particular paths in the graph which is naturally associated with the system.     

Algebraic approach to controller design using structured singular value

The aim of this paper is to show an algebraic approach to controller design using the structured singular value (denoted μ) as a robust stability and performance indicator. The algebraic μ-synthesis is applied to three different problems–time-delay systems, the HIMAT vehicle model and the two-tank system. A way of treating general delayed systems with uncertain time delays via the linear fractional transformation is shown. A simple controller is derived, which handles uncertain time delay in both the numerator and denominator of an anisochronic system. The overall performance is verified by simulations for all systems and compared with the D–K iteration.     

Structural modelling and integrative analysis of microelectromechanical systems product using graph theoretic approach

Micro-electromechanical systems (MEMS) as an enabling technology is seen to play a more and more important role for the main stream of industry of the future by broadening its applications to information, communications and bio technologies. Development of MEMS devices, however, still relies on knowledge and experience of MEMS experts due to the design and fabrication process complexity. It is difficult to understand the trade-offs inherent in the system and achieve an optimal structure without any MEMS-related insight. An attempt is made to develop an integrated systems model for the complete structure of the MEMS product system in terms of its constituents and interactions between the constituents. The hierarchical tree structures of the MEMS system and its subsystems are presented up to component level. For characterization, analysis and identification of MEMS product system, three different mathematical models say graph theoretic model, matrix model and permanent model are presented. These models are associated with graph theory, matrix method and variable permanent function by considering the various subsystems, subsubsystems up to component level, their connectivity and interdependency of the MEMS product system. The developed methodology is explained with an example. The proposed modeling and analysis is extendable to the subsystems and the component level. An overall structural analysis can be carried out by following a ‘top-down’ approach or ‘bottom-up’ approach. Understanding of MEMS product structure will help in the improvement of performance, cost, design time, and so on.