The synchronized graphs trace the context-sensitive languages

Morvan and Stirling have proved that the context-sensitive languages are exactly the traces of graphs defined by transducers with labelled final states. We prove that this result is still true if we restrict to the traces of graphs defined by synchronized transducers with labelled final states. From their construction, we deduce that the context-sensitive languages are the languages of path labels leading from and to rational vertex sets of letter-to-letter rational graphs.     

Linearly bounded infinite graphs

Linearly bounded Turing machines have been mainly studied as acceptors for context-sensitive languages. We define a natural class of infinite automata representing their observable computational behavior, called linearly bounded graphs. These automata naturally accept the same languages as the linearly bounded machines defining them. We present some of their structural properties as well as alternative characterizations in terms of rewriting systems and context-sensitive transductions. Finally, we compare these graphs to rational graphs, which are another class of automata accepting the context-sensitive languages, and prove that in the bounded-degree case, rational graphs are a strict sub-class of linearly bounded graphs.A preliminary version of this article appeared in MFCS 2005.     

An automaton generating series of graphs

The developmental process of a multicellular organism is considered as a series of graphs, whose nodes correspond to cells, and edges to cellular interconnections. We introduce here a new mechanism, called a rational machine, for generating series of finite directed graphs. With biological applications in mind, each node is named with a string of symbols. First the growth rate of graphs is analyzed. The generative capability of a rational machine is shown with many examples. Decision problems and closure properties under operations are also discussed. Among other things, it is shown that whether two rational machines generate the same graph series is undecidable.     

On the transition graphs of turing machines

As for pushdown automata, we consider labelled Turing machines with ε-rules. With any Turing machine M and with a rational set C of configurations, we associate the restriction to C of the ϵ-closure of the transition set of M. We get the same family of graphs by using the labelled word rewriting systems. We show that this family is the set of graphs obtained from the binary tree by applying an inverse mapping into F followed by a rational restriction, where F is any family of recursively enumerable languages containing the rational closure of all linear languages. We show also that this family is obtained from the rational graphs by inverse rational mappings. Finally we show that this family is also the set of graphs recognized by (unlabelled) Turing machines with labelled final states, and even if we restrict to deterministic Turing machines.     

Graph compression and the zeros of polynomials

We explore a novel quantitative relationship between the compressibility of directed graphs and the disposition of the zeros of polynomials with rational coefficients. The connection highlights the genericity of incompressible graphs and the genericity of polynomials all of whose zeros are simple.     

A Kleene Theorem for a Class of Planar Acyclic Graphs

In this paper, we study planar directed ordered connected acyclic graphs, in particular graphs that can be built over a (finite) doubly ranked alphabet by parallel and serial composition. On the one hand we introduce finite automata on graphs and, on the other hand, rational expressions that involve union, nondeterministic parallel composition, serial composition, and the iterations of these compositions. We prove a Kleene Theorem linking these two characterizations of sets of graphs.     

An Internal Presentation of Regular Graphs by Prefix-Recognizable Graphs

The study of infinite graphs has potential applications in the specification and verification of infinite systems and in the transformation of such systems. Prefix-recognizable graphs and regular graphs are of particular interest in this area since their monadic second-order theories are decidable. Although the latter form a proper subclass of the former, no characterization of regular graphs within the class of prefix-recognizable ones has been known, except for a graph-theoretic one in [2]. We provide here three such new characterizations. In particular, a decidable, language-theoretic, necessary and sufficient condition for the regularity of any prefix-recognizable graph is established. Our proofs yield a construction of a deterministic hyperedge-replacement grammar for any prefix-recognizable graph that is regular. Received July 19, 1999, and in revised form December 22, 2000, and in final form March 28, 2001. Online publication July 20, 2001.     

The synthesis of Petri nets from path-automatic specifications

Path-automatic specifications are rational presentations of sets of finite or infinite graphs. A specification is made of a regular set of paths and rational relations on this set. Each action is specified by two relations that define, respectively, when it may, or must occur. Two other relations tell which pairs of paths may not, or must be confluent. We show that it is decidable whether some model of a path-automatic specification may be realized by some finite Petri net with transitions in bijection with the specified actions.     

Inference of structures of models of probabilistic dependences from statistical data

Problems of reconstruction of structures of probabilistic dependence models in the class of directed (oriented) acyclic graphs (DAGs) and mono-flow graphs are considered. (Mono-flow graphs form a subclass of DAGs in which the cycles with one collider are prohibited.) The technique of induced (provoked) dependences is investigated and its application to the identification of structures of models is shown. The algorithm “Collifinder-M” is developed that identifies all collider variables (i.e., solves an intermediate problem of reconstruction of the structure of a mono-flow model). It is shown that a generalization of the technique of induced dependences makes it possible to strengthen well-known rules of identification of orientation of edges in a DAG model. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 19–31, November–December 2005.     

A note on pure and <Emphasis Type="Italic">p</Emphasis>-pure languages

A variation of first order logic with variables for exponents is developed to solve some problems in the setting of rational languages on the free monoid, implying in particular algorithms for purity and p-purity. This same problem is addressed for the case of rational free group languages, and characterizations of the rational subsets of involved are also obtained.Received: 5 December 2002, Pedro V. Silva: http://www.fc.up.pt/cmup     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

A distance measure for large graphs based on prime graphs

Graphs are universal modeling tools. They are used to represent objects and their relationships in almost all domains: they are used to represent DNA, images, videos, social networks, XML documents, etc. When objects are represented by graphs, the problem of their comparison is a problem of comparing graphs. Comparing objects is a key task in our daily life. It is the core of a search engine, the backbone of a mining tool, etc. Nowadays, comparing objects faces the challenge of the large amount of data that this task must deal with. Moreover, when graphs are used to model these objects, it is known that graph comparison is very complex and computationally hard especially for large graphs. So, research on simplifying graph comparison gainedan interest and several solutions are proposed. In this paper, we explore and evaluate a new solution for the comparison of large graphs. Our approach relies on a compact encoding of graphs called prime graphs. Prime graphs are smaller and simpler than the original ones but they retain the structure and properties of the encoded graphs. We propose to approximate the similarity between two graphs by comparing the corresponding prime graphs. Simulations results show that this approach is effective for large graphs.     

A graph isomorphism algorithm for object recognition

We present an algorithm to solve the graph isomorphism problem for the purpose of object recognition. Objects, such as those which exist in a robot workspace, may be represented by labelled graphs (graphs with attributes on their nodes and/or edges). Thereafter, object recognition is achieved by matching pairs of these graphs. Assuming that all objects are sufficiently different so that their corresponding representative graphs are distinct, then given a new graph, the algorthm efficiently finds the isomorphic stored graph (if it exists). The algorithm consists of three phases: preprocessing, link construction, and ambiguity resolution. Results from experiments on a wide variety and sizes of graphs are reported. Results are also reported for experiments on recognising graphs that represent protein molecules. The algorithm works for all types of graphs except for a class of highly ambiguous graphs which includes strongly regular graphs. However, members of this class are detected in polynomial time, which leaves the option of switching to a higher complexity algorithm if desired.     

Coalgebraic Monads

This paper introduces coalgebraic monads as a unified model of term algebras covering fundamental examples such as initial algebras, final coalgebras, rational terms and term graphs. We develop a general method for obtaining finitary coalgebraic monads which allows us to generalise the notion of rational term and term graph to categories other than Set. As an application we sketch part of the correctness of the the term graph implementation of functional programming languages.     

A closed-form optimal control for linear systems with equal state and input delays

This paper presents the optimal regulator for a linear system with equal delays in state and input and a quadratic criterion. The optimal regulator equations are obtained using the maximum principle. Performance of the obtained optimal regulator is verified in the illustrative example against the best linear regulators available for the linear system without delays and for a rational approximation of the original time delay system. Simulation graphs demonstrating better performance of the obtained optimal regulator are included.     

一类完备的正交分段多项式函数系及其应用

在几何图形或图像边界的频谱分析应用中,用Fourier三角基表示间断图形时必然会出现Gibbs现象,而用Walsh函数表示时,因其收敛速度慢而效果欠佳.本文首先构造了一类分段点在四进制有理数点处的分段多项式函数集(简称四进制U-系统,QU-系统),它是L2[0,1]空间上的完备的正交函数系,并研究了它的性质、基函数与Fourier-QU系数的计算公式,同时,也给出了1～3次QU-系统的一组显式表达式.然后,使用Fourier-QU级数的有限项和表示图像轮廓线,提出用有限的Fourier-QU系数描述几何图形或图像轮廓线,并由此得到了一类新的多项式描述子——QU描述子,而归一化QU描述子是一类基于平移、旋转与尺度变换的特征不变量.最后,通过数值实验证实了使用Fourier-QU级数逼近一元平方可积函数时,其收敛速率要优于Fourier级数、Walsh级数和Fourier-BU级数,同样也验证了QU描述子是一类有效的形状描述子,用图像间的QU距离能准确地描述图像间的相似性.     

Algorithms for induced biclique optimization problems

We present polynomial time algorithms for induced biclique optimization problems in the following families of graphs: polygon-circle graphs, 4-hole-free graphs, complements of interval-filament graphs and complements of subtree-filament graphs. Such problems are to find maximum: induced bicliques, induced balanced bicliques and induced edge bicliques. These problems have applications for biclique clustering of proteins by PPI criteria, of documents, and of web pages.     

On Nonlinear Parametric Search

An alternative viewpoint for parametric search is presented, which achieves a bound similar to that of Cole's improvement on Megiddo's method. The new technique simulates the algorithm for the underlying fixed-parameter problem simultaneously over multiple computation paths and applies naturally to linear and nonlinear problems. The uses of the method are illustrated with examples from optimization on weighted graphs and dynamic geometry, including maximum spanning trees, diameter, and smallest enclosing ball. Received January 6, 1998; revised December 21, 1998.     

The distant-2 chromatic number of random proximity and random geometric graphs

We are interested in finding bounds for the distant-2 chromatic number of geometric graphs drawn from different models. We consider two undirected models of random graphs: random geometric graphs and random proximity graphs for which sharp connectivity thresholds have been shown. We are interested in a.a.s. connected graphs close just above the connectivity threshold. For such subfamilies of random graphs we show that the distant-2-chromatic number is Θ(logn) with high probability. The result on random geometric graphs is extended to the random sector graphs defined in [J. Díaz, J. Petit, M. Serna. A random graph model for optical networks of sensors, IEEE Transactions on Mobile Computing 2 (2003) 143-154].     

Compiling conceptual graphs

The paper addresses problems in conceptual graph implementation: subsumption and classification in a taxonomy. Conceptual graphs are typically stored using a directed acyclic graph data structure based on the partial order over conceptual graphs. We give an improved algorithm for classifying conceptual graphs into this hierarchy. It prunes the search space in the database using the information gathered while searching. We show how conceptual graphs in this hierarchy can be compiled into instructions which represent specialized cases of the canonical formation rules. This compiles subsumption of conceptual graphs and compresses knowledge in a knowledge base. Conceptual graphs are compiled as differences between adjacent graphs in the hierarchy. The differences represent the rules used in deriving the graph from the adjacent graphs. We illustrate how the method compresses knowledge bases in some experiments. Compilation is effected in three ways: removal of redundant data, use of simple instructions which ignore redundant checks when performing matching, and by sharing common processing between graphs