Fundamenta Informaticae - Volume 26, issue 3-4

Authors: Engels, G. | Ehrig, H. | Rozenberg, G.

Article Type: Other

DOI: 10.3233/FI-1996-263410

Citation: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 205-205, 1996

Authors: Ariola, Zena M. | Klop, Jan Willem

Article Type: Research Article

Abstract: We present an equational framework for term graph rewriting with cycles. The usual notion of homomorphism is phrased in terms of the notion of bisimulation, which is well-known in process algebra and concurrency theory. Specifically, a homomorphism is a functional bisimulation. We prove that the bisimilarity class of a term graph, partially ordered by functional bisimulation, is a complete lattice. It is shown how Equational Logic induces a notion of copying and substitution on term graphs, or systems of recursion equations, and also suggests the introduction of hidden or nameless nodes in a term graph. Hidden nodes can be used …only once. The general framework of term graphs with copying is compared with the more restricted copying facilities embodied in the μ-rule. Next, orthogonal term graph rewrite systems, also in the presence of copying and hidden nodes, are shown to be confluent. Show more

DOI: 10.3233/FI-1996-263401

Citation: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 207-240, 1996

Authors: Corradini, A. | Montanari, U. | Rossi, F.

Article Type: Research Article

Abstract: We first give a new definition of graph grammars, which, although following the algebraic double-pushout approach, is more general than the classical one because of the use of a graph of types where all involved graphs are mapped to. Then, we develop a process-based semantics for such (typed) graph grammars, in the line of processes as normally used for providing a semantics to Petri nets. More precisely, we represent each equivalence class of derivations as a graph process, which can be seen as an acyclic graph grammar, plus a mapping of its items onto the items of the given grammar. …Finally, we show that such processes represent exactly the equivalence classes of derivations up to the well-known shift-equivalence, which have always been used in the literature on graph grammars. Therefore graph processes are attractive alternative representatives for such classes. The advantage of dealing with graph processes instead of equivalence classes (or also representatives belonging to the equivalence classes) is that dependency and/or concurrency of derivation steps is explicitly represented. Show more

DOI: 10.3233/FI-1996-263402

Citation: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 241-265, 1996

Authors: Drewes, Frank

Article Type: Research Article

Abstract: Tree transducers may be used to perform symbolic computations. A function f from (the domain of) one algebra into (the domain of) another algebra is computed by a transduction that yields for every term representing an element a of the input algebra a term representing f(a) in the target algebra. We consider the case where the input algebra is a term algebra, the target algebra is given by the natural numbers with monotonic operations (and in particular maximum, addition, and multiplication), and f is injective. Such an injective function may be seen as a coding of terms as natural numbers. …It is shown that codings computed by top-down tree transducers cannot compress totally balanced trees: The binary representation of f(t) has at least the size of t up to a constant factor. Show more

DOI: 10.3233/FI-1996-263403

Citation: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 267-285, 1996

Authors: Habel, Annegret | Heckel, Reiko | Taentzer, Gabriele

Article Type: Research Article

Abstract: In each graph-grammar approach it is defined how and under which conditions graph productions can be applied to a given graph in order to obtain a derived graph. The conditions under which productions can be applied are called application conditions. Although the generative power of most of the known general graph-grammar approaches is sufficient to generate any recursively enumerable set of graphs, it is often convenient to have specific application conditions for each production. Such application conditions, on the one hand, include context conditions like the existence or non-existence of nodes, edges, or certain subgraphs in the given graph as …well as embedding restrictions concerning the morphisms from the left-hand side of the production to the given graph. In this paper, the concept of application conditions introduced by Ehrig and Habel is restricted to contextual conditions, especially negative ones. In addition to the general concept, we state local confluence and the Parallelism Theorem for derivations with application conditions. Finally we study context-free graph grammars with application conditions with respect to their generative power. Show more

Keywords: graph grammars, graph transformation systems, application conditions, contextual conditions

DOI: 10.3233/FI-1996-263404

Citation: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 287-313, 1996

Authors: Janssens, D. | Mens, T.

Article Type: Research Article

Abstract: ESM systems are a graph-rewriting formalism for concurrent systems: a global system state is represented by a graph and a run of the system is described by a graph rewriting process. These rewriting processes are formally described by computation structures. It is demonstrated that the computation structures of an ESM system P may be viewed as the arrows of a category Catcomp (P) where objects are system states. This category generalizes the well-known notion of a transition system. From Catcomp (P) various more abstract semantics are derived, and for each of them a powerful composition operation on computations, generalizing both …the sequential and parallel composition of computations, is defined. Show more

DOI: 10.3233/FI-1996-263405

Citation: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 315-339, 1996

Authors: Mosbah, Mohamed

Article Type: Research Article

Abstract: In a probabilistic graph grammar, each production has a probability attached to it. This induces a probability assigned to each derivation tree, and to each derived graph. Conditions for this probability function to be a probabilistic measure are discussed. The statistical properties of the generated language are investigated. We show how to compute the average size of an inductive function, and the probability of an inductive graph predicate. A relationship can be established between production probabilities and some statistical information of the generated language. This way, probabilities can be assigned to productions so that the generated graphs satisfy some statistical …condition. Show more

DOI: 10.3233/FI-1996-263406

Citation: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 341-362, 1996

Authors: Schürr, Andy

Article Type: Research Article

Abstract: This paper presents a new logic based framework for the formal treatment of graph rewriting systems as special cases of programmed rewriting systems for arbitrary relational structures. Considering its expressive power, the new formalism surpasses almost all variants of nonparallel algebraic as well as algorithmic graph grammar approaches by offering set-oriented pattern matching facilities as well as nonmonotonic reasoning capabilities for checking pre- and postconditions of rewrite rules. Furthermore, the formalism closes the gap between the operation-oriented manipulation of data structures by means of rewrite rules and the declaration-oriented description of data structures by means of logic based languages. Finally, …the formalism even offers recursively defined (sub-)programs, by means of which the application of rewrite rules may be regulated. A denotational semantics definition for these (sub-)programs relies on a special variant of fixpoint theory for noncontinuous but monotonic functions. Show more

DOI: 10.3233/FI-1996-263407

Citation: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 363-385, 1996

Authors: Taentzer, Gabriele

Article Type: Research Article

Abstract: Synchronous and asynchronous graph transformations are discussed on the basis of distributed graph transformations. All types of graph transformations presented are formulated in the single-pushout approach to graph transformations and compared with each other. Some criteria are given to preserve or reestablish synchrony according to the definition proposed in this paper.

DOI: 10.3233/FI-1996-263408

Citation: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 387-406, 1996

Authors: Wagner, Annika | Gogolla, Martin

Article Type: Research Article

Abstract: A single pushout approach to the transformation of attributed partial graphs based on categories of partial algebras and partial morphisms is introduced. A sufficient condition for pushouts in these categories is presented. As the synchronization mechanism we use amalgamation of rules and show how synchronization can be minimized. We point out how the results obtained can be employed in order to define an operational semantics for object specification languages.

DOI: 10.3233/FI-1996-263409

Citation: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 407-431, 1996