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

CREATORAlexis de Colnet, Kuldeep S. Meel, Umang Mathur
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE154 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-00314

Browse the full library · About the Tower of Babel