3 papers
cs.DS2022
Reduction ratio of the IS-algorithm: worst and random cases
Vincent Jugé
We study the IS-algorithm, a well-known linear-time algorithm for computing the suffix array of a word. This algorithm relies on transforming the input word into another word,…
math.CO2017
Uniform generation of infinite concurrent runs: the case of trace monoids
Samy Abbes, Vincent Jugé
We introduce an algorithm for the uniform generation of infinite runs in concurrent systems under a partial order probabilistic semantics. We work with trace monoids as concurrency…
math.AG2017
Counting bi-colored A'Campo forests
Noémie Combe, Vincent Jugé
We give an efficient method of counting bi-colored A'Campo forests and provide a stratification criterion for the space of those graphs. We deduce an algorithm to count these fores…