Deciding Sparseness of Regular Languages of Finite Trees and Infinite Words
Kord Eickmeyer, Georg Schindling · 2025
Read Deciding Sparseness of Regular Languages of Finite Trees and Infinite Words by Kord Eickmeyer, Georg Schindling (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-2507-03465.txt.
Description
Kord Eickmeyer and Georg Schindling ask when a well-behaved language is secretly almost empty. A tree language is sparse if its share of all trees shrinks to zero as trees grow. A language of infinite words is sparse if it fills measure zero of the natural probability space. The pair prove sparseness is decidable for regular languages in both worlds.
For trees they give characterizations through forbidden subtrees and automata, yielding a linear-time test. For infinite words the route runs through infix completeness, with a fresh decidability proof. Better, when a language is not sparse their algorithm exhibits a measurable block of accepted words, usable as counterexamples in almost-sure model checking. Applications reach from formal verification to XML schemas.
Catalog record
| CREATOR | Kord Eickmeyer, Georg Schindling |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-03465