Hyperedge replacement: grammars and languages

Publication date 20 September 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

bibliography Hyperedge-Replacement Grammars hypergraph languages

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Grammars and rewriting systems (68Q42) Graph theory (including graph drawing) in computer science (68R10)

Review text

The book (it is an enlarged version of author's doctoral dissertation, Bremen Univ., 1989) systematically investigates Hyperedge-Replacement Grammars (HRG) and associated languages (HRL), generalizing the theory of edge replacement systems in such a way that ``several major constructions and results known from the classical theory of context-free Chomsky grammars and languages remain valid for HRG and corresponding hypergraph languages (from the Foreword by \textit{H. Ehrig}). Here is, in short, the content of the eight chapters: (I) Introduction to HRG: basic definitions, examples, motivation, the basic operation of replacing a hyperedge by a hypergraph (Def. 2.1) and of HRG (Def. 3.1, 3.2), normal form theorems; (II) Basic properties of HRG's: parallel derivations, derivation trees, structure of derivations; (III) Characterizations of HRL's: closure properties (\(X\)-substitution, iterated \(X\)-substitution, etc.), a Kleene type characterization, a fixed-point theorem; (IV) Structural aspects of HRL's: simplification of HRG (reduced HRG), decidability of emptiness and membership, pumping lemma, consequences (decidability of finiteness), counterexamples, semilinearity (Parikh theorem); (V) Generative power of HRG's: the graph generating power of HRG, string-graph languages; (VI) Graph-theoretic aspects of HRL's: graph properties compatible with the hyperedge replacement (with a large list of examples), their decidability (the powerful ``metatheorem for decision problem - Theorem 4.1 -- shows that if a graph-theoretic property \(P\) is compatible with respect to some class \(C\) of hyperedge replacement grammars, then for all \(G\in C\) it is decidable whether (1) \(P\) holds for some graph in \(L(G)\) and (2) \(P\) holds for all graphs in \(L(G)\)), non-compatible properties, undecidability results; (VII) Boundedness aspects of HRL's: decidability of questions of the form ``given a graph parameter and a HRG, it is decidable whereas the values of this parameter over all graphs generated by this HRG are bounded?, compatible predicates and compatible functions, the decidability of their boundedness (a ``metatheorem for boundedness problems -- Theorem 3.1 -- is given, with a series of consequences), undecidable problems; (VIII) Extensions and variants of HRG's: hypergraph-replacement grammars, parallel HRG as a hypergraph version of ET0L systems, figure-generating grammars. Each chapter starts with an informal presentation of the material to be exposed and end with a bibliographical note. The monograph end with a comprehensive bibliography, a list of symbols and an index of notions. The notions are gradually introduced and well illustrated, the results are followed by complete proofs, and their consequences are fully exploited; in general, the book provides a useful and pleasant reading.

Cited in

(only showing first 100 items - show all)

This page was built for publication: Hyperedge replacement: grammars and languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q684560)