29 citations · 67 across the 15 of their papers we have counts for
4 papers · 1 filter
Non-redundant random generation algorithms for weighted context-free languages
Andy Lorenz, Yann Ponty
We address the non-redundant random generation of words of length in a context-free language. Additionally, we want to avoid a predefined set of words. We study a rejection…
Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots
Philippe Rinaudo, Yann Ponty, Dominique Barth +1
We present a general setting for structure-sequence comparison in a large class of RNA structures that unifies and generalizes a number of recent works on specific families on stru…
Rule-weighted and terminal-weighted context-free grammars have identical expressivity
Yann Ponty
Two formalisms, both based on context-free grammars, have recently been proposed as a basis for a non-uniform random generation of combinatorial objects. The former, introduced by…
The weighted words collector
Jérémie Du Boisberranger, Danièle Gardy, Yann Ponty
Motivated by applications in bioinformatics, we consider the word collector problem, i.e. the expected number of calls to a random weighted generator of words of length before…