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

CREATORKord Eickmeyer, Georg Schindling
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-03465

Browse the full library · About the Tower of Babel