2026/04/29 by Madina Bazarova, Faruk Alpay · 1 voice
Computer Science · #cs.FL #cs.LO
paper · pdf · doi:10.48550/arxiv.2604.27024
We introduce the finite-horizon first-order rank profile of a language L ⊆ Σ^*: the least quantifier rank needed by an FO[<] sentence to classify membership in L correctly on all words of length at most n. The invariant measures quantifier depth only; formula size is deliberately not bounded. First, we prove a rank calculus that is independent of regularity. Every language satisfies ρL(n) ≤ \lceil log2 n \rceil + 4, via balanced first-order distance formulas and exact-word definitions. Moreover, supn ρL(n) < ∞ holds exactly when L is globally FO[<]-definable, and the supremum equals the minimum quantifier rank of such a definition. Second, for regular languages we prove a sharp aperiodicity gap: if the syntactic monoid of L is aperiodic, then ρL(n) = O(1); otherwise ρL(n) = log2 n + OL(1). The lower bound extracts a nontrivial cyclic component from the syntactic monoid and combines it with an Ehrenfeucht-Fraisse power lemma for long repetitions of a fixed word. Thus, for full FO[<] quantifier rank, regular languages admit no intermediate finite-horizon growth between bounded and logarithmic rank.