The Trichotomy of Regular Property Testing
Gabriel Bathie, Nathanaël Fijalkow, Corto Mascle · 2025
Read The Trichotomy of Regular Property Testing by Gabriel Bathie, Nathanaël Fijalkow, Corto Mascle (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-2504-19152.txt.
Description
Gabriel Bathie, Nathanaël Fijalkow, and Corto Mascle published a 2025 computer science paper classifying how hard it is to test regular languages. Property testing asks a cheap question: by sampling a few positions of a long word, can we tell whether it belongs to a language, or is far from any word that does? A 2001 paper opened this field for regular languages, those recognized by simple finite machines.
The authors prove the landscape splits into exactly three classes. Each class has its own best possible number of queries. Better, they characterize which languages fall where using a concrete combinatorial tool: minimal blocking sequences, patterns read straight off the machine. The analysis reasons directly about automata rather than through heavy machinery. The trichotomy settles the complexity map for a classic problem. It also feeds streaming algorithms, where the same sampling logic decides what a data stream contains.
Catalog record
| CREATOR | Gabriel Bathie, Nathanaël Fijalkow, Corto Mascle |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 133 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19152