A comparison of boundary graph grammars and context-free hypergraph grammars

The purpose of this paper is to compare the (language) generative power of context-free hypergraph grammars (CFHG) and boundary graph grammars (B-edNCE). These generative mechanisms are different in nature: edge placing versus node placing and, much more, directed hypergraphs generators versus graph generators. Some technical results are thus in order: normal forms for B-edNCE, some closure properties of B-edNCE and, of course, a definition of hypergraphs representations as graphs (and vice-versa). CFHG and B-edNCE (of bounded nonterminal degree) are shown to have the same power (as graphs, and also as hypergraphs generators). Arbitrary B-edNCE have the same hypergraph generative power as the CFHG, but, as graph generators, their power strictly increases. The paper is almost self-contained, partly because of the lack of widely accepted definitions for the studied classes of grammars.

Recommendations

Cites work

Cited in

(36)

This page was built for publication: A comparison of boundary graph grammars and context-free hypergraph grammars

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