2 papers
cs.FL2025
Counting and Sampling Traces in Regular Languages
Alexis de Colnet, Kuldeep S. Meel, Umang Mathur
In this work, we study the problems of counting and sampling Mazurkiewicz traces that a regular language touches. Fix an alphabet and an independence relation $\mathbb{I} \sub…
cs.DS2025
Towards practical FPRAS for #NFA: Exploiting the Power of Dependence
Kuldeep S. Meel, Alexis de Colnet
#NFA refers to the problem of counting the words of length accepted by a non-deterministic finite automaton. #NFA is #P-hard, and although fully-polynomial-time randomized appr…