{"ID":2835084,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.00314","arxiv_id":"2512.00314","title":"Counting and Sampling Traces in Regular Languages","abstract":"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} \\subseteq Σ\\times Σ$. The input consists of a regular language $L \\subseteq Σ^*$, given by a finite automaton with $m$ states, and a natural number $n$ (in unary). For the counting problem, the goal is to compute the number of Mazurkiewicz traces (induced by $\\mathbb{I}$) that intersect the $n^\\text{th}$ slice $L_n = L \\cap Σ^n$, i.e., traces that admit at least one linearization in $L_n$. For the sampling problem, the goal is to output a trace drawn from a distribution that is approximately uniform over all such traces. These tasks are motivated by bounded model checking with partial-order reduction, where an \\emph{a priori} estimate of the reduced state space is valuable, and by testing methods for concurrent programs that use partial-order-aware random exploration. We first show that the counting problem is #P-hard even when $L$ is accepted by a deterministic automaton, in sharp contrast to counting words of a DFA, which is polynomial-time solvable. We then prove that the problem lies in #P for both NFAs and DFAs, irrespective of whether $L$ is trace-closed. Our main algorithmic contributions are a \\emph{fully polynomial-time randomized approximation scheme} (FPRAS) that, with high probability, approximates the desired count within a prescribed accuracy, and a \\emph{fully polynomial-time almost uniform sampler} (FPAUS) that generates traces whose distribution is provably close to uniform.","short_abstract":"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} \\subseteq Σ\\times Σ$. The input consists of a regular language $L \\subseteq Σ^*$, given by a finite automaton with $m$ states, and a natural numb...","url_abs":"https://arxiv.org/abs/2512.00314","url_pdf":"https://arxiv.org/pdf/2512.00314v1","authors":"[\"Alexis de Colnet\",\"Kuldeep S. Meel\",\"Umang Mathur\"]","published":"2025-11-29T04:28:27Z","proceeding":"cs.FL","tasks":"[\"cs.FL\",\"cs.CC\",\"cs.LO\",\"cs.PL\"]","methods":"[\"LoRA\"]","has_code":false}