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.
DOI: https://doi.org/10.2478/puma-2022-0002 | Journal eISSN: 1788-800X
Language: English
Page range: 1 - 7
Submitted on: Mar 31, 2022
Accepted on: May 15, 2022
Published on: Jun 18, 2022
Published by: Corvinus University of Budapest
In partnership with: Paradigm Publishing Services
Publication frequency: 4 issues per year
Related subjects:
© 2022 Samy Abbes, Vincent Jugé, published by Corvinus University of Budapest
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.