Counting and Sampling Traces in Regular Languages
Alexis de Colnet, Kuldeep S. Meel, Umang Mathur · 2025
Read Counting and Sampling Traces in Regular Languages by Alexis de Colnet, Kuldeep S. Meel, Umang Mathur (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-00314.txt.
Introduction
Counting the traces a formal language can produce is a basic question in theoretical computer science. Alexis de Colnet, Kuldeep Meel, and Umang Mathur study counting and sampling traces in regular languages in 2025. Traces account for which actions can run independently and commute.
The setup fixes an alphabet with an independence relation, a regular language given by a finite automaton, and a length given in unary. Counting and sampling underpin verification of concurrent systems, where independent actions interleave freely. The work clarifies how hard these problems are, guiding tool builders who model real concurrent software. Regular languages are the simplest language class, which makes the hardness results sharper.
Catalog record
| CREATOR | Alexis de Colnet, Kuldeep S. Meel, Umang Mathur |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 154 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-00314