<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>We introduce an algorithm for the uniform generation of infinite traces, <italic>i.e.</italic>, 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.</p>
</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.

Uniform generation of infinite traces

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Uniform generation of infinite traces"}

We introduce an algorithm for the uniform generation of infinite traces, i.e., infinite words up to commutation of some letters. The algorithm outputs...

Uniform generation of infinite traces

Publié en ligne: 18 juin 2022

Pages: 1 - 7

Reçu: 31 mars 2022

Accepté: 15 mai 2022

DOI: https://doi.org/10.2478/puma-2022-0002

Mots clés
trace monoid, Möbius polynomial, uniform measure, random generation

© 2022 Samy Abbes et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Uniform generation of infinite traces

Publié en ligne: 18 juin 2022

Pages: 1 - 7

Reçu: 31 mars 2022

Accepté: 15 mai 2022

DOI: https://doi.org/10.2478/puma-2022-0002

Mots cléstrace monoid, Möbius polynomial, uniform measure, random generation

© 2022 Samy Abbes et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
trace monoid, Möbius polynomial, uniform measure, random generation