@article{10.1145_3776723,
    author = {de Colnet, Alexis and Meel, Kuldeep S. and Mathur, Umang},
    title = {Counting and Sampling Traces in Regular Languages},
    year = {2026},
    issue_date = {January 2026},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    volume = {10},
    number = {POPL},
    url = {https://doi.org/10.1145/3776723},
    doi = {10.1145/3776723},
    abstract = {In this work, we study the fundamental problems of counting and sampling traces that a regular language touches. Formally, one fixes the alphabet Σ and an independence relation I ⊆ Σ \texttimes{} Σ. The computational problems we address take as input a regular language L over Σ, presented as a finite automaton with m states, together with a natural number n (presented in unary). For the counting problem, the output is the number of Mazurkiewicz traces (induced by I) that intersect the nth slice Ln = L ∩ Σn of L, i.e., traces that have at least one linearization in Ln. For the sampling problem, the output is a trace drawn from a distribution that is approximately uniform over all such traces. These problems are motivated by applications such as bounded model checking based on partial-order reduction, where an a priori estimate of the size of the state space can significantly improve usability, as well as testing approaches for concurrent programs that use partial-order-aware random sampling, where uniform exploration is desirable for effective bug detection. We first show that the counting problem is #P-hard even when the automaton accepting the language L is deterministic, which is in sharp contrast to the corresponding problem for counting the words of a DFA, which is solvable in polynomial time. We then show that the counting problem remains in the class #P for both NFAs and DFAs, independent of whether L is trace-closed. Finally, our main contributions are a fully polynomial-time randomized approximation scheme (FPRAS) that, with high probability, estimates the desired count within a specified accuracy parameter, and a fully polynomial-time almost uniform sampler (FPAUS) that generates traces while ensuring that the distribution induced on them is approximately uniform with high probability.},
    journal = {Proc. ACM Program. Lang.},
    month = {jan},
    articleno = {81},
    numpages = {28},
    keywords = {FPRAS, Mazurkiewicz traces, approximate counting, complexity, counting, regular language, sampling},
    date-added = {2026-1-9 10:0:43 +0100}
}

@article{10.1145_3776723, author = {de Colnet, Alexis and Meel, Kuldeep S. and Mathur, Umang}, title = {Counting and Sampling Traces in Regular Languages}, year = {2026}, issue_date = {January 2026}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, volume = {10}, number = {POPL}, url = {https://doi.org/10.1145/3776723}, doi = {10.1145/3776723}, abstract = {In this work, we study the fundamental problems of counting and sampling traces that a regular language touches. Formally, one fixes the alphabet Σ and an independence relation I ⊆ Σ \texttimes{} Σ. The computational problems we address take as input a regular language L over Σ, presented as a finite automaton with m states, together with a natural number n (presented in unary). For the counting problem, the output is the number of Mazurkiewicz traces (induced by I) that intersect the nth slice Ln = L ∩ Σn of L, i.e., traces that have at least one linearization in Ln. For the sampling problem, the output is a trace drawn from a distribution that is approximately uniform over all such traces. These problems are motivated by applications such as bounded model checking based on partial-order reduction, where an a priori estimate of the size of the state space can significantly improve usability, as well as testing approaches for concurrent programs that use partial-order-aware random sampling, where uniform exploration is desirable for effective bug detection. We first show that the counting problem is #P-hard even when the automaton accepting the language L is deterministic, which is in sharp contrast to the corresponding problem for counting the words of a DFA, which is solvable in polynomial time. We then show that the counting problem remains in the class #P for both NFAs and DFAs, independent of whether L is trace-closed. Finally, our main contributions are a fully polynomial-time randomized approximation scheme (FPRAS) that, with high probability, estimates the desired count within a specified accuracy parameter, and a fully polynomial-time almost uniform sampler (FPAUS) that generates traces while ensuring that the distribution induced on them is approximately uniform with high probability.}, journal = {Proc. ACM Program. Lang.}, month = {jan}, articleno = {81}, numpages = {28}, keywords = {FPRAS, Mazurkiewicz traces, approximate counting, complexity, counting, regular language, sampling}, date-added = {2026-1-9 10:0:43 +0100} }