<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

Online veröffentlicht: 18. Juni 2022

Seitenbereich: 1 - 7

Eingereicht: 31. März 2022

Akzeptiert: 15. Mai 2022

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

Schlüsselwörter
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

Online veröffentlicht: 18. Juni 2022

Seitenbereich: 1 - 7

Eingereicht: 31. März 2022

Akzeptiert: 15. Mai 2022

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

Schlüsselwörtertrace 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.

Schlüsselwörter
trace monoid, Möbius polynomial, uniform measure, random generation