Parsing of edNLC-graph grammars for scene analysis

An edNLC-graph grammar, introduced by Janssens,⁽⁴⁾ is a strong formalism for generating scene representations. This grammar generates directed node- and edge-labelled graphs, EDG-graphs. A method of construction of unambiguous string EDG-graph representation is briefly described. The characteristics of edNLC-graph grammar for syntactic pattern recognition allows us to construct the parsing algorithm. The deterministic top-down syntax analyzer is constructed for the subfamily of an edNLC-graph grammar, called an ETL/1-graph grammar. An ETL/1-graph grammar is parallel to a finite state string grammar. The notions introduced in the paper are useful for researches in less restricted edNLC-graph grammars, for example grammars analogical to context-free string grammars.     

Symbolic graphs for attributed graph constraints

In this paper we present a new class of graphs, called symbolic graphs, to define a new class of constraints on attributed graphs. In particular, in the first part of the paper, we study the category of symbolic graphs showing that it satisfies some properties, which are the basis for the work that we present in the second part of the paper, where we study how to reason with attributed graph constraints. More precisely, we define a set of inference rules, which are the instantiation of the inference rules defined in a previous paper, for reasoning about constraints on standard graphs, showing their soundness and (weak) completeness. Moreover, the proof of soundness and completeness is also an instantiation of the corresponding proof for standard graph constraints, using the categorical properties studied in the first part of the paper. Finally, we show that adding a new inference rule makes our system sound and strongly complete.     

Automated reasoning for attributed graph properties

Graphs are ubiquitous in computer science. Moreover, in various application fields, graphs are equipped with attributes to express additional information such as names of entities or weights of relationships. Due to the pervasiveness of attributed graphs, it is highly important to have the means to express properties on attributed graphs to strengthen modeling capabilities and to enable analysis. Firstly, we introduce a new logic of attributed graph properties, where the graph part and attribution part are neatly separated. The graph part is equivalent to first-order logic on graphs as introduced by Courcelle. It employs graph morphisms to allow the specification of complex graph patterns. The attribution part is added to this graph part by reverting to the symbolic approach to graph attribution, where attributes are represented symbolically by variables whose possible values are specified by a set of constraints making use of algebraic specifications. Secondly, we extend our refutationally complete tableau-based reasoning method as well as our symbolic model generation approach for graph properties to attributed graph properties. Due to the new logic mentioned above, neatly separating the graph and attribution parts, and the categorical constructions employed only on a more abstract level, we can leave the graph part of the algorithms seemingly unchanged. For the integration of the attribution part into the algorithms, we use an oracle, allowing for flexible adoption of different available SMT solvers in the actual implementation. Finally, our automated reasoning approach for attributed graph properties is implemented in the tool AutoGraph integrating in particular the SMT solver Z3 for the attribute part of the properties. We motivate and illustrate our work with a particular application scenario on graph database query validation.     

Compilation of functional languages using flow graph analysis

A system based on the notion of a flow graph is used to specify formally and to implement a compiler for a lazy functional language. The compiler takes a simple functional language as input and generates C. The generated C program can then be compiled, and loaded with an extensive run-time system to provide the facility to experiment with different analysis techniques. The compiler provides a single, unified, efficient, formal framework for all the analysis and synthesis phases, including the generation of C. Many of the standard techniques, such as strictness and boxing analyses, have been included.     

Recognizability of graph and pattern languages

Graph language recognizability is defined and investigated by virtue of the syntactic magmoid, analogously with the syntactic monoid of a word language. In this setup, the syntax complexity of a given recognizable graph language can be determined, giving rise to a syntactic classification inside the class of recognizable graph languages.     

新型属性图文法反应式规约验证方法

属性图文法广泛应用在软件设计阶段建模和分析阶段。命题式时序逻辑（propositional temporal logic）无法直接表达建模实体包含随时间演化的关联属性反应式规约,提出一种可支持通用图文法转换系统中相应规约的验证方法,通过引入标记节点及属性,将包含相应关联属性的规约公式等价转换为命题式时序逻辑,从而可以间接支持该类型规约的验证。以流行的对象式属性图文法模型检测工具GROOVE为平台,结合启发案例,验证了所提出方法的有效性。     

Extensions to query languages for graph traversal problems

Extensions to database query languages for retrievals that involve inferencing on the nodes and edges of a graph are surveyed. Common types of inferencing are to find paths between two nodes, compute a value for a path such as a distance or an elapsed time, and to choose among alternative paths. The survey is based on the data model (relational or functional), method of extension (iteration, recursion, or special operators), interface style (string or tabular), and restrictions (data- and problem-oriented). The Quel, objected-oriented functional data, G-Whin, and Alpha languages are examined in detail with different values for these properties. The characteristics of other languages are summarized in several tables. The results of the survey indicate the diversity of language extensions and the need to provide data-model and query-language features to address such problems     

A survey of typical attributed graph queries

World Wide Web - Graphs are commonly used for representing complex structures such as social relationships, biological interactions, and knowledge bases. In many scenarios, graphs not only...     

Deep graph transformation for attributed,directed, and signed networks

Knowledge and Information Systems - Generalized from image and language translation, the goal of graph translation or transformation is to generate a graph of the target domain on the condition of...     

Efficient recognition algorithms for boundary and linear eNCE graph languages

It is well known that every boundary (linear) eNCE graph language that is connected and degree-bounded by a constant is in LOGCFL (NLOG). The present paper proves an upper bound of the complexity of boundary (linear) eNCE graph languages whose component and degree bounds are functions in the size of the graph. As a corollary of this analysis, the known LOGCFL and NLOG results stated above hold even if “connected” is replaced by “component-bounded by log n.” Received: 15 January 1997 / 17 January 2001     

CAMAS: A cluster-aware multiagent system for attributed graph clustering

Attributed graphs describe nodes via attribute vectors and also relationships between different nodes via edges. To partition nodes into clusters with tighter correlations, an effective way is applying clustering techniques on attributed graphs based on various criteria such as node connectivity and/or attribute similarity. Even though clusters typically form around nodes with tight edges and similar attributes, existing methods have only focused on one of these two data modalities. In this paper, we comprehend each node as an autonomous agent and develop an accurate and scalable multiagent system for extracting overlapping clusters in attributed graphs. First, a kernel function with a tunable bandwidth factor δ is introduced to measure the influence of each agent, and those agents with highest local influence can be viewed as the “leader” agents. Then, a novel local expansion strategy is proposed, which can be applied by each leader agent to absorb the most relevant followers in the graph. Finally, we design the cluster-aware multiagent system (CAMAS), in which agents communicate with each other freely under an efficient communication mechanism. Using the proposed multiagent system, we are able to uncover the optimal overlapping cluster configuration, i.e. nodes within one cluster are not only connected closely with each other but also with similar attributes. Our method is highly efficient, and the computational time is shown that nearly linearly dependent on the number of edges when δ ∈ [0.5, 1). Finally, applications of the proposed method on a variety of synthetic benchmark graphs and real-life attributed graphs are demonstrated to verify the systematic performance.     

Visual graph modeling for scene recognition and mobile robot localization

Image retrieval and categorization may need to consider several types of visual features and spatial information between them (e.g., different point of views of an image). This paper presents a novel approach that exploits an extension of the language modeling approach from information retrieval to the problem of graph-based image retrieval and categorization. Such versatile graph model is needed to represent the multiple points of views of images. A language model is defined on such graphs to handle a fast graph matching. We present the experiments achieved with several instances of the proposed model on two collections of images: one composed of 3,849 touristic images and another composed of 3,633 images captured by a mobile robot. Experimental results show that using visual graph model (VGM) improves the accuracies of the results of the standard language model (LM) and outperforms the Support Vector Machine (SVM) method.     

On the structure of node-label-controlled graph languages

A new kind of graph grammars (called NLC grammars) is introduced. The main theorem is a result on the combinatorial structure of graph languages generated by NLC grammars; it resembles the pumping theorem for context-free string languages.     

Efficient nonparametric and asymptotic Bayesian model selection methods for attributed graph clustering

Attributed graph clustering, also known as community detection on attributed graphs, attracts much interests recently due to the ubiquity of attributed graphs in real life. Many existing algorithms have been proposed for this problem, which are either distance based or model based. However, model selection in attributed graph clustering has not been well addressed, that is, most existing algorithms assume the cluster number to be known a priori. In this paper, we propose two efficient approaches for attributed graph clustering with automatic model selection. The first approach is a popular Bayesian nonparametric method, while the second approach is an asymptotic method based on a recently proposed model selection criterion, factorized information criterion. Experimental results on both synthetic and real datasets demonstrate that our approaches for attributed graph clustering with automatic model selection significantly outperform the state-of-the-art algorithm.     

Context-free graph languages of bounded degree are generated by apex graph grammars

The apex graph grammars generate precisely the context-free graph languages of bounded degree, independently of whether one considers hyperedge replacement systems or (boundary or confluent) NLC or edNCE graph grammars. The main feature of apex graph grammars is that nodes cannot be passed from nonterminal to nonterminal. The proof is based on a normal form result for arbitrary hyperedge replacement systems that forbids passing chains. This generalizes Greibach Normal Form.     

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.