Hypermap rewriting: A combinatorial approach (Q1178702)

A graph grammar [\textit{V. Claus}, \textit{H. Ehrig} and \textit{G. Rozenberg}, Graph grammars and their applications to computer science, Lecture Notes in Computer Science, Vol. 13, 153, 291 (1980, 1983, 1987)] is essentially a formalized way of generating a family of graphs by re-writing a subgraph --- that is replacing it with another subgraph. This concept was generalized to hypergraphs [\textit{A. Habel} and \textit{H. J. Kreowski}, Theor. Comput. Sci. 51, 81-115 (1987; Zbl 0636.68100)] and to combinatorial maps, graphs in which a cyclic order is assigned to the edge-ends incident to each vertex [\textit{S. Lins}, Graph-encoded maps, J. Comb. Theory, Ser. B, Vol. 32, 171-181 (1982; Zbl 0478.05040 (preview Zbl 0465.05031))]. The paper under review extends it to combinatorial hypermaps (hypergraphs in which vertex-hyperedge incidence pairs are cyclically ordered at each vertex and at each hyperedge). A general hypermap grammar, in which an arbitrary sub-hypermap can be rewritten, is shown to be powerful enough to simulate an arbitrary Turing machine or an arbitrary context-sensitive Chomsky grammar, whereas an \(H\)-grammar, in which only a hyperedge can be rewritten, can be simulated by a context-free Chomsky grammar. It follows that several questions about \(L(G)\), the language of a hypermap grammar \(G\), are undecidable if \(G\) is an arbitrary hypermap grammar but decidable if \(G\) is an \(H\)-grammar. These include: (1) is \(L(G)\) empty? (2) does \(L(G)\) contain only maps? (3) does \(L(G)\) contain only connected hypermaps? Finally, a pumping lemma for \(H\)-grammars shows that not all families of hypermaps can be generted by \(H\)-grammars.