💻 computer science

Finite-Horizon First-Order Rank Profiles of Regular Languages

This paper introduces the finite-horizon first-order rank profile to measure the quantifier depth required for language classification on words of bounded length, establishing that for regular languages, this rank exhibits a sharp dichotomy where it remains constant if and only if the language is aperiodic, otherwise growing logarithmically with word length.

Original authors: Madina Bazarova, Faruk Alpay

Published 2026-05-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Madina Bazarova, Faruk Alpay

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a librarian trying to sort a massive collection of books (words) into two piles: "Accepted" and "Rejected." The catch is that you can only look at books up to a certain thickness (length $n$ ). You want to write a set of rules (a logical sentence) to decide which pile a book belongs to.

The paper asks a very specific question: How "deep" do your rules need to be to get the sorting right for all books up to thickness $n$ ?

In the world of computer science, this "depth" is called quantifier rank. Think of it like the number of nested "If... then..." or "There exists..." steps in your rule.

Low rank: Simple rules like "If the book starts with 'A', put it in the Accepted pile."
High rank: Complex, nested rules like "If there is a chapter that starts with 'A', and inside that chapter there is a sentence that starts with 'B', and that sentence is followed by..."

The authors, Madina Bazarova and Faruk Alpay, discovered a fascinating "gap" in how complex these rules must get, depending on the type of library (language) you are dealing with.

The Two Types of Libraries

The paper divides all possible libraries into two distinct categories based on their internal structure (mathematically called the "syntactic monoid").

1. The "Simple" Libraries (Star-Free / Aperiodic)

Some libraries have a very rigid, non-repeating structure. They don't have complex, endless loops.

The Finding: For these libraries, the complexity of your rules stays constant, no matter how thick the books get.
The Analogy: Imagine a library where the rule is simply "No books with more than 3 red pages." Whether you are sorting books that are 10 pages thick or 1,000 pages thick, the rule remains the same simple sentence. You never need to add more layers of "If/Then" logic just because the books are getting bigger.
The Math: The rule complexity is $O(1)$ (constant).

2. The "Complex" Libraries (Regular but not Star-Free)

Other libraries have a structure that relies on repeating patterns or cycles (like a clock that ticks 1-2-3-1-2-3...).

The Finding: For these libraries, as the books get thicker, your rules must get more complex, but only at a very specific, slow pace.
The Analogy: Imagine a library where the rule is "Accept books if the total number of pages is even." To check if a 10-page book is even, you need a simple check. To check a 1,000-page book, you need a slightly deeper check. To check a 1,000,000-page book, you need a deeper check still.
The "Gap": The paper proves that the complexity cannot stay low (like the simple libraries), but it also cannot explode wildly. It grows exactly at the speed of a logarithm.
The Math: The rule complexity grows as $\log_2 n$ .

What is a Logarithm in this context?

Think of a logarithm as a "binary search" or a "doubling" scale.

To sort books up to length 10, you need a tiny bit of depth.
To sort books up to length 100, you don't need 10 times more depth; you only need a little bit more (because 100 is just $10 \times 10$ , but in log scale, it's just a small jump).
To sort books up to length 1,000,000, you need a manageable amount of extra depth, not a million times more.

The authors call this the "Aperiodicity Gap." There is no middle ground. A library is either:

Simple: Rules stay the same size forever.
Complex: Rules grow slowly (logarithmically).
There is no library where the rules grow at a medium speed (like a square root) or a fast speed (like a polynomial). It's a sharp cliff between "constant" and "logarithmic."

How Did They Prove This?

The Upper Bound (The "Brute Force" Method):
The authors showed that for any library, no matter how weird, you can always write a rule that works for books up to length $n$ with a depth of about $\log_2 n$ .

The Trick: You can write a specific rule for every single book up to length $n$ that says "This exact book is accepted" or "This exact book is rejected."
The Cost: While the depth of the rule is small (logarithmic), the size of the rule (how many words it contains) might be huge—like a phone book listing every single book. But the paper only cares about the depth of the logic, not how long the sentence is.

The Lower Bound (The "Indistinguishable Twins" Method):
For the complex libraries, they proved you cannot do better than logarithmic depth.

The Trick: They found pairs of "twin" books that look identical to any shallow rule but have different lengths.
The Logic: If you have a rule with a shallow depth (say, depth 5), it can't tell the difference between a book with 100 pages and a book with 101 pages if they follow a repeating pattern. To tell them apart, you need to dig deeper into the logic.
The Result: The deeper the books get, the deeper your logic must be to spot the difference. This forces the complexity to grow as $\log_2 n$ .

Summary for the General Audience

This paper is about measuring the "mental effort" (logic depth) required to sort words of increasing length.

If the language is "Star-Free" (simple structure): The mental effort is constant. You never need to think harder as the words get longer.
If the language is "Regular but not Star-Free" (repeating structure): The mental effort grows, but very slowly (logarithmically). It's the most efficient growth possible for complex patterns.
The Big Discovery: There is no "medium" complexity. You either have a simple pattern that requires constant effort, or a complex pattern that requires logarithmic effort. There is no in-between.

The paper does not discuss medical applications, AI training, or future technologies. It is a pure mathematical investigation into the fundamental limits of how we describe patterns using logic.

1. Problem Statement

The paper investigates the quantitative complexity of classifying languages using First-Order Logic with order ($FO[<]$) under a finite-horizon constraint.

Context: Classically, the Schützenberger–McNaughton–Papert theorem establishes that a regular language is definable in $FO[<]$ if and only if its syntactic monoid is aperiodic (star-free).
The Gap: While global definability is a binary property (definable or not), the paper asks: How much quantifier depth is required to correctly classify a language on words of length at most $n$ ?
Definition: The finite-horizon rank profile, denoted $\rho_L(n)$ , is defined as the minimum quantifier rank $q$ such that an $FO[<]$ sentence of rank $q$ correctly distinguishes all words in $L \cap \Sigma^{\leq n}$ from those not in $L$ .
Key Distinction: The metric focuses solely on quantifier rank (nesting depth), not formula size. The authors acknowledge that formulas of logarithmic rank may be exponentially large in size, but the question is strictly about the minimum depth of quantification required.

2. Methodology

The authors employ a combination of model-theoretic techniques (Ehrenfeucht–Fraïssé games) and algebraic automata theory (syntactic monoids).

A. Model-Theoretic Foundations

Rank- $q$ Equivalence ( $\equiv_q$ ): Two words $u, v$ are equivalent if they satisfy the same $FO[<]$ sentences of quantifier rank $\leq q$ . This is characterized by the Duplicator winning the $q$ -round Ehrenfeucht–Fraïssé game.
Exact-Word Definitions: The authors construct specific formulas to define exact words or lengths.
- They introduce balanced distance formulas ( $Dist_d(x, y)$ ) that define a distance of $d$ between positions using a recursive "divide and conquer" strategy.
- Key Lemma: The quantifier rank of $Dist_d$ is bounded by $\lceil \log_2 d \rceil + 1$ .
- This allows the construction of an "exact-word" formula $\chi_w$ for any word $w$ of length $m$ with rank $\approx \log_2 m$ .

B. Algebraic Analysis

Syntactic Monoids: For regular languages, the authors analyze the structure of the syntactic monoid $Syn(L)$.
Aperiodicity vs. Periodicity:
- If $Syn(L)$ is aperiodic, the language is globally $FO[<]$-definable.
- If $Syn(L)$ is not aperiodic, it contains a non-trivial group (a cyclic component).
Power Lemma: They utilize the fact that for a fixed word $x$ , the words $x^m$ and $x^{m'}$ are indistinguishable by rank- $q$ formulas if $m, m' \geq 2^q$ . This is extended to "contexted powers" ( $rx^ms$ ).

3. Key Contributions and Results

I. Universal Upper Bound (Arbitrary Languages)

For any language $L$ (regular or not) and any horizon $n$ :
$\rho_L(n) \leq \lceil \log_2 n \rceil + 4$

Mechanism: By disjoining exact-word formulas for all accepted words of length $\leq n$ .
Significance: This proves that logarithmic rank is sufficient to classify any language on a finite horizon, regardless of its complexity. The cost is formula size (exponential), not rank.

II. Boundedness Characterization

The profile $\rho_L(n)$ is bounded (i.e., $\sup_n \rho_L(n) < \infty$ ) if and only if $L$ is globally definable in $FO[<]$.

If $L \in FO[<]$ , there exists a fixed $q$ such that $\rho_L(n) \leq q$ for all $n$ .
If $L \notin FO[<]$ , the rank must grow with $n$ .

III. The Aperiodicity Gap (Main Theorem for Regular Languages)

For regular languages, the growth of $\rho_L(n)$ exhibits a sharp dichotomy with no intermediate growth rates:

Case A: Aperiodic Syntactic Monoid (Star-Free)
- $Syn(L)$ is aperiodic $\iff$ $L \in FO[<]$ .
- Result: $\rho_L(n) = O(1)$ . The rank is bounded by a constant independent of $n$ .
Case B: Non-Aperiodic Syntactic Monoid (Not Star-Free)
- $Syn(L)$ contains a non-trivial group.
- Result: $\rho_L(n) = \log_2 n + O_L(1)$ .
- Lower Bound Proof: The authors extract a "contexted periodic power" $rx^ks$ from the monoid. Using the Power Lemma, they show that for $n$ large enough, one can find two words $u, v$ of length $\leq n$ (one in $L$ , one not) such that $u \equiv_q v$ for any $q \leq \log_2 n - O(1)$ . Thus, rank must grow logarithmically to distinguish them.

Summary of the Dichotomy:
$\rho_L(n) = \begin{cases} O(1) & \text{if } L \text{ is star-free} \\ \log_2 n + O(1) & \text{if } L \text{ is regular but not star-free} \end{cases}$

IV. Unary Regular Languages

The paper applies this to unary languages ( $L \subseteq \{a\}^*$ ).

$L$ is $FO[<]$-definable $\iff$ $L$ is finite or cofinite.
If $L$ is neither (e.g., modular arithmetic like "length is even"), the rank grows as $\log_2 n$ .

4. Significance and Implications

Refinement of Classical Theory: The paper moves beyond the binary "definable vs. not definable" classification of the Schützenberger–McNaughton–Papert theorem. It quantifies how far a non-star-free language is from being definable by measuring the rate at which the required quantifier depth grows.
Rigidity of Growth: A major theoretical contribution is the proof that for regular languages, there are no intermediate growth rates (e.g., $\sqrt{n}$ or $\log \log n$ ). The complexity is either constant or strictly logarithmic.
Resource Separation: The work highlights the distinction between quantifier rank and formula size. It shows that while non-star-free languages require increasing rank to distinguish inputs, they can still be classified with low rank if one is willing to accept exponentially large formulas (via the exact-word construction).
Future Directions: The authors identify open problems regarding:
- Rank-Size Tradeoffs: What is the Pareto frontier between rank and formula size?
- Fragment Profiles: Does this dichotomy hold for restricted fragments like $FO^2[<]$ or positive logic? (The paper suggests the proof does not immediately transfer).
- Separator Growth: How does the rank behave when separating two disjoint regular languages rather than classifying one?

Conclusion

The paper establishes that the finite-horizon first-order rank profile is a precise measure of the algebraic complexity of regular languages. It proves that the transition from star-free to non-star-free regular languages manifests as a sharp jump from constant quantifier depth to logarithmic quantifier depth, providing a new quantitative perspective on the limits of first-order logic.