graphgrammars can easily be considered as models for rule-based systems where solving state-space problems essentially requires searching. Since many AI problems are naturally graphical, graphgrammars could narrow t...
详细信息
ISBN:
(纸本)9783540544784
graphgrammars can easily be considered as models for rule-based systems where solving state-space problems essentially requires searching. Since many AI problems are naturally graphical, graphgrammars could narrow the usual gap between a problem and its formal specification. In order to be able to solve such problems in practice one must reduce the effort of search. Here, for graph grammar specifications, the idea of precomputing its rules allows to prune the corresponding search-trees safely by explicitly pointing to those subtrees which are contained in others. Moreover, for some rules it becomes possible to use the information of a rule's former for to predict its later non-applicability, thus avoiding some redundant, expensive applicability tests. the example of solving a domino game based on breadth-first search demonstrates that indeed some remarkable reductions can be obtained.
To avoid paradoxes in parallel graph rewriting, it is desirable to forbid overlapping instances of a subgraph to be rewritten simultaneously. the selection of maximal sets of nonoverlapping instances corresponds to th...
详细信息
ISBN:
(纸本)9783540544784
To avoid paradoxes in parallel graph rewriting, it is desirable to forbid overlapping instances of a subgraph to be rewritten simultaneously. the selection of maximal sets of nonoverlapping instances corresponds to the selection of maximal independent sets of nodes in a derived graph. this note briefly examines the process of repeatedly selecting such sets of nodes. It shows that doing so ''decimates'' the graph in the sense that the number of nodes shrinks exponentially;but that unfortunately, the degree of the graph may grow exponentially.
graphgrammars, especially when enriched with attributes, can be used as a powerful software engineering technique. the main idea behind this approach is: A problem domain is modelled by a graph, the representation gr...
详细信息
ISBN:
(纸本)9783540544784
graphgrammars, especially when enriched with attributes, can be used as a powerful software engineering technique. the main idea behind this approach is: A problem domain is modelled by a graph, the representation graph, whose nodes correspond to the objects of the domain and whose edges to the relations between the objects, respectively. Typical operations which normally change the structure of the representation graph, like introducing new objects at a certain state of the problem description, or modifying relations between objects, are expressed by graph productions. Quantitative informations are handled by the attributes attached to the nodes of the representation graph. So, the implementation aspects are reduced to a very general and flexible data structure, namely graphs.
the Very High Level language PROGRESS presented within this paper is the first statically typed language which is based on the concepts of PROgrammed graph RE-writing SyStems. this language supports different programm...
详细信息
ISBN:
(纸本)9783540544784
the Very High Level language PROGRESS presented within this paper is the first statically typed language which is based on the concepts of PROgrammed graph RE-writing SyStems. this language supports different programming paradigms by offering procedural and declarative programming constructs for the definition of integrity constraints, functional attribute dependencies, derived binary relationships, atomic graph rewrite rules, and complex graph transformations. Boththe language and its underlying formalism are based on experiences of about ten years with a model-oriented approach to the specification of document classes and document processing tools (of the Integrated Programming Support ENviroment IPSEN). this approach, called graph grammar engineering, is characterized by using attributed graphs to model object structures. Programmed graph rewriting systems are used to specify operations in terms of their effect on these graph models. this paper informally introduces PROGRESS' underlying graph grammar formalism and demonstrates its systematic use by specifying parts of a syntax-directed editor for a simple expression language. the construction of a PROGRESS-specific environment with an integrated set of tools is the topic of another paper within this volume (cf. /NS 90/).
this paper illustrates the use of graphgrammars for specifying concurrent systems and languages. the model used in this paper, Δ-grammars, is rooted in existing graph grammar theory and provides a convenient framewo...
详细信息
A graph language L is in the class C-edNCE of context-free NCE graph languages if and only if L = f(T) where f is a function on graphs that can be defined in monadic second-order logic and T is the set of’all trees o...
详细信息
While in general the recognition problem for (hyper-)edge replacement grammars is NP-complete, there are polynomial algorithms for restricted graph classes. the degree of the corresponding polynomial depends on the si...
详细信息
Configuration spaces are considered where arbitrary objects are placed in a two-dimensional discretized space and can move via translations and rotations within this space. If there is a motion of an object or even if...
详细信息
Algebraic specification grammars have recently been introduced implicitly by the second author as a new kind of graph granmm~ in order to generate algebraic specifications using productions and derivations. In fact, i...
详细信息
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...
详细信息
暂无评论