Finite-Horizon First-Order Rank Profiles of Regular Languages
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911633427660800 |
|---|---|
| author | Bazarova, Madina Alpay, Faruk |
| author_facet | Bazarova, Madina Alpay, Faruk |
| contents | We introduce the finite-horizon first-order rank profile of a language $L \subseteq Σ^*$: the least quantifier rank needed by an $\mathrm{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) \le \lceil \log_2 n \rceil + 4$, via balanced first-order distance formulas and exact-word definitions. Moreover, $\sup_n ρ_L(n) < \infty$ holds exactly when $L$ is globally $\mathrm{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) = \log_2 n + O_L(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 $\mathrm{FO}[<]$ quantifier rank, regular languages admit no intermediate finite-horizon growth between bounded and logarithmic rank. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_27024 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Finite-Horizon First-Order Rank Profiles of Regular Languages Bazarova, Madina Alpay, Faruk Formal Languages and Automata Theory Logic in Computer Science 03D05, 03C13, 68Q45, 03B25 We introduce the finite-horizon first-order rank profile of a language $L \subseteq Σ^*$: the least quantifier rank needed by an $\mathrm{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) \le \lceil \log_2 n \rceil + 4$, via balanced first-order distance formulas and exact-word definitions. Moreover, $\sup_n ρ_L(n) < \infty$ holds exactly when $L$ is globally $\mathrm{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) = \log_2 n + O_L(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 $\mathrm{FO}[<]$ quantifier rank, regular languages admit no intermediate finite-horizon growth between bounded and logarithmic rank. |
| title | Finite-Horizon First-Order Rank Profiles of Regular Languages |
| topic | Formal Languages and Automata Theory Logic in Computer Science 03D05, 03C13, 68Q45, 03B25 |
| url | https://arxiv.org/abs/2604.27024 |