ANNULLATO - Seminario di Logica ed Informatica Teorica

Venerdì 15 settembre 2023 alle ore 12:00, Federico Vastarini (University of York, UK) terrà il Seminario di Logica ed Informatica Teorica dal titolo "Random Graph Generation in Context-Free Graph Languages".

Abstract:
We present a novel approach to the generation of random hypergraphs in user-specified domains. Our method extends a method of Mairson for generating strings in context-free languages to the settingof context-free hypergraph languages specified by hyperedge replacement grammars. Generating (or “sampling") graphs and hypergraphs according to a given probability distributions is a problem thatfinds application in testing algorithms and programs working on graphs. Other potential applicationareas include molecular biology and post-quantum cryptography.
Our generation algorithm uses as input a hyperedge replacement grammar in Chomsky normalform and a positive integern. The former specifies the hypergraph language to sample from, the latter the size of the hypergraph to be generated. The algorithm then chooses a hypergraph at randomfrom the slice of the language consisting of all members of sizen. We show that if the grammaris non-ambiguous, the generated samples are uniformly distributed. The only requirements for our method are that the properties sought for the generated hypergraphs are representable by a hyperedge replacement language and that, to guarantee a uniform distribution, a non-ambiguous grammar isused as input.
We also show that our method generates a random hypergraph of sizenin timeO(n2). This is the same time bound established by Mairson (for his first method) in the setting of random stringgeneration in context-free languages.

Il seminario si svolgerà in presenza presso il Dipartimento di Matematica e Fisica,
Lungotevere Dante, 376 - Aula M4

Via Teams al seguente Link