2 papers
cs.DS2026
Efficient Uniform Sampling of Surjections via their Profiles
Arnaud Carayol, Pablo Rotondo
In this article, we develop efficient sampling algorithms for random surjections from to for all . We make no assumption about and . In particular, we…
cs.FL2025
Random Deterministic Automata With One Added Transition
Arnaud Carayol, Philippe Duchon, Florent Koechlin +1
Every language recognized by a non-deterministic finite automaton can be recognized by a deterministic automaton, at the cost of a potential increase of the number of states, which…