<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

Data publikacji: 18 cze 2022

Zakres stron: 1 - 7

Otrzymano: 31 mar 2022

Przyjęty: 15 maj 2022

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

Słowa kluczowe
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

Data publikacji: 18 cze 2022

Zakres stron: 1 - 7

Otrzymano: 31 mar 2022

Przyjęty: 15 maj 2022

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

Słowa kluczowetrace 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.

Słowa kluczowe
trace monoid, Möbius polynomial, uniform measure, random generation