Uniform generation of infinite traces
Samy Abbes, Vincent Jugé · Pure mathematics and applications · 2022
Abstract We introduce an algorithm for the uniform generation of infinite traces, i.e. , infinite words up to commutation of some letters. The algorithm outputs on-the-fly approximations of a theoretical infinite trace, the latter being distributed according to the exact uniform probability measure. The average size of the approximation grows linearly with the time of execution of the algorithm, provided that some–costly–precomputations have been done.