Hypermap rewriting: a combinatorial approach

AbstractCombinatorial hypermaps may be viewed as topological representations of hypergraphs. In this paper, we introduce a hypermap rewriting model based on a purely combinatorial formulation of the rewriting mechanism. We illustrate this model by providing a hypermap grammar which generates the set of all connected planar maps. We also investigate a special kind of hypermap grammars, the H-grammars, for which we give a pumping theorem enlightening the combinatorial structure of the generated hypermap languages. Finally, we give some decidability results concerning hypermap grammars and H-grammars