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

CREATORGabriel Bathie, Nathanaël Fijalkow, Corto Mascle
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE133 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-19152

Browse the full library · About the Tower of Babel