Can I read Random Graph Generation in Context-Free Graph Languages on EtoBox?

Random Graph Generation in Context-Free Graph Languages by Vastarini, Federico; Plump, Detlef is a scholarly article available to read on EtoBox.

What is Random Graph Generation in Context-Free Graph Languages about?

We present a method for generating random hypergraphs in context-free hypergraph languages. It is obtained by adapting Mairson's generation algorithm for context-free string grammars to the setting of hyperedge replacement grammars. Our main results are that for non-ambiguous hyperedge replacement grammars, the method generates hypergraphs uniformly at random and in quadratic time. We illustrate our approach by a running example of a hyperedge replacement grammar generating term graphs.

Author

Vastarini, Federico; Plump, Detlef

Published

2024

Language

EN