<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

Pubblicato online: 18 giu 2022

Pagine: 1 - 7

Ricevuto: 31 mar 2022

Accettato: 15 mag 2022

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

Parole chiave
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

Pubblicato online: 18 giu 2022

Pagine: 1 - 7

Ricevuto: 31 mar 2022

Accettato: 15 mag 2022

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

Parole chiavetrace 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.

Parole chiave
trace monoid, Möbius polynomial, uniform measure, random generation