Hypergraph languages of bounded degree

摘要

Two types of hypergraph rewriting grammar are considered: the well-known context-free hypergraph grammar (or CFHG grammar, also known as hyperedge replacement system or HR system) and the more recent separated handle hypergraph grammar (or S-HH grammar). It is shown that every S-HH hypergraph language of bounded (hyper-)degree can be generated by a (separated) CFHG grammar. This implies that these two types of grammar generate the same class of graph languages of bounded degree, but incomparable classes of hypergraph languages.