Procedure graphs are directed graphs with arc labels denoting precedence, useful in modelling computer algorithms. Equivalent procedure graphs yield the same data outcome under identical inputs, yet imply different pe...
详细信息
A survey type presentation, introducing the theory of graphoids and their representation in graphs. graphoids are ternary relations over a finite domain governed by a finite set of axioms. they are intended as models ...
详细信息
ISBN:
(纸本)9783540544784
A survey type presentation, introducing the theory of graphoids and their representation in graphs. graphoids are ternary relations over a finite domain governed by a finite set of axioms. they are intended as models for the representation of irrelevance relations of the form I(X,Z,Y) where (X,Z,Y) in I has the following interpretation: given that the values of the variables in Z are known, the values of the variables in Y can add no further information about the values of the variables in X.
We present a definition of term graph rewriting as the taking of a pushout in a category of partial morphisms, adapting the rather ad hoc definitions we gave in [Ken87] so as to use a standard category-theoretic conce...
详细信息
ISBN:
(纸本)9783540544784
We present a definition of term graph rewriting as the taking of a pushout in a category of partial morphisms, adapting the rather ad hoc definitions we gave in [Ken87] so as to use a standard category-theoretic concept of partial morphism. this single-pushout construction is shown to coincide withthe well-known double-pushout description of graph rewriting whenever the latter is defined. In general, the conditions for the single pushout to exist are weaker than those required for the double pushout. In some categories of graphs, no conditions at all are necessary.
the algebraic approach to graphgrammars - well-known in the literature for several types of graphs and structures - is extended to include several new types of replacement systems, especially the roplacement of algeb...
详细信息
Layout graphgrammars are extensions of context-free graphgrammars and are introduced as a tool for syntax directed constructions of graph layouts. the constructions are based on a layout specification of the product...
详细信息
Relational structures form a unique framework in which various types of graphs and hypergraphs can be formalized and studied. We define operations on structures that are compatible with monadic second-order logic, and...
详细信息
ISBN:
(纸本)9783540544784
Relational structures form a unique framework in which various types of graphs and hypergraphs can be formalized and studied. We define operations on structures that are compatible with monadic second-order logic, and that are powerful enough to represent context-free graph- and hypergraph-grammers of various types, namely, hyperedge replacement, C-edNCE, and separated handle replacement ones. Several results on monadic second-order properties of the generated sets are obtained in a uniform way.
Term rewriting is commonly implemented by graph reduction in order to improve efficiency. In general, however, graph reduction is not complete: a term may be not normalizable through graph derivations although a norma...
详细信息
In this paper, the computational power of the noetherian graph Relabelling systems with Priorities (PGRS for short) is studied. the PGRS’s are considered as recognizers for sets of graphs and for sets of 1-sourced gr...
详细信息
Triple graphgrammars (TGGs) have been invented 15 years ago as a formalism for the declarative specification of bidirectional graph-to-graph translations. In this paper we present a list of still open problems concer...
详细信息
ISBN:
(纸本)9783540874041
Triple graphgrammars (TGGs) have been invented 15 years ago as a formalism for the declarative specification of bidirectional graph-to-graph translations. In this paper we present a list of still open problems concerning the interpretation and the expressiveness of TGGs. We will comment on extensions proposed to improve the original approach and the drawbacks that arise thereof. Consequently a more precise formalization of compulsory properties of the translation of triple graphgrammars into forward and backward graph translation functions is given. Regarding these properties an interpretation and implementation of negative application conditions is derived that does not destroy the benefits of the original approach. Additionally a new demand-driven forward/backward translation rule application strategy is proposed. It guarantees for the first time automatically a correct ordering of rule applications without imposing any additional requirements on the structure of the regarded graphs.
In this paper, we introduce and study the notion of collage grammars. A collage (in our sense) consists essentially of a set of parts being geometric objects and a set of hyperedges being subjects of further replaceme...
详细信息
暂无评论