Counting and Sampling Traces in Regular Languages
summary
Problem: count Mazurkiewicz traces of length n that intersect a regular language presented as an m‑state automaton; hardness: exact counting is #P‑hard already for deterministic automata. Main claims: a polynomial‑time randomized approximation (FPRAS) and an almost‑uniform sampler (FPAUS) for traces. Key techniques: unroll the automaton into layered acyclic graph, use union‑of‑sets estimators with canonical representative samples and a polynomial‑time membership predictive test. Complexity depends on the independence width γ; sample sets stay polynomial (roughly quadratic) and the algorithm proves they do not blow up.
AI-written summary · about