×

An economical transformation of graph grammars. (English) Zbl 0802.68074

Summary: The main result is a technical contribution in the theory of so called labeled graphs \((l\)-graphs). We present a more economical transformation of a certain type of monotonic graph grammar G to equivalent context-free graph grammar G’. The best result previously known was quadratic size of the part of G’ corresponding to a single production of G. Our main result is an improvement which gives linear size reductions.

MSC:

68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1. E. GROTSCH and M. NAGL, Explicit Versus Implicit Parallel Rewriting on Graphs, LNCS Springer-Verlag, N73, 1979, pp. 237-254. Zbl0412.68060 MR565043 · Zbl 0412.68060
[2] 2. L. LEVY and YUEH KANG, On Labeled Graph Grammars, Computing, 20, 1978, pp. 109-125. Zbl0376.68045 MR619764 · Zbl 0376.68045 · doi:10.1007/BF02252341
[3] 3. M. NAGL, Graph-Grammatiken Theorie, Anwendungen, Implementierung, Wiesbaden, 1979. Zbl0517.68069 MR562308 · Zbl 0517.68069
[4] 4. M. NAGL, A tutorial and bibliographical survey on graph grammars, LCNS, Springer-Verlag, N73, 1979, pp.70-126. Zbl0414.68040 MR565035 · Zbl 0414.68040
[5] 5. M. NAGL, Set Theoretic Approaches to Graph Grammars. NLCS, Springer-Verlag, N291, 1987, pp.41-54. Zbl0643.68115 · Zbl 0643.68115
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.