Random Uniform walK In Automata

Rukia is a C++ library to generate paths (or traces) in automata according to a defined coverage criterion. Thus, it provides generic algorithms to count the number of elements to be covered, and generic algorithms to explore automata at random while ensuring a uniform distribution among those elements.

Intellectual property


lgpl Rukia is a free software: see the Lesser GNU Public license (LGPL). So basically, this means that you are free to use it anywhere but you need to make available any modification you did.

Rukia is also deposited in the Agency for the protection of programs (APP):

  • IDDN.FR.001.350014.000.S.C.2009.000.00000

How it works?

View experimental results

To understand how to use the Rukia library, the simplest way is to download the archive and refer to the README file inside.

If you are still not convinced by the interest of using Rukia instead of classical (isotropic) random walks, please compare the results from our experiments. Even better, try it on your models and send me back your results.


Some publications that use Rukia


  • A new dichotomic algorithm for the uniform random generation of words in regular languages. Theoretical Computer Science (2012),doi:10.1016/j.tcs.2012.07.025 [ pdf ]


  • Johan Oudinet, Alain Denise, Marie-Claude Gaudel, Richard Lassaigne and Sylvain Peyronnet. Uniform Monte-Carlo Model checking. In FASE, Conference on Fundamental Approaches to Software Engineering, Saarbrücken, Germany, March 2011, 10 pages. [ pdf ]


  • Johan Oudinet. Exploration aléatoire de modèles. In MSR, colloque francophone sur la Modélisation des Systèmes Réactifs, Volume 43 of Journal européen des systèmes automatisés (JESA), Nantes, France, pages 905-919, November 2009. [ pdf ]