The Alternation Hierarchy of First-Order Logic on Words is Decidable

Michaël CadilhacarXiv 2025 · DOI · arXiv

TL;DR

This paper proves that it's decidable whether a given regular language can be expressed in a specific fragment of first-order logic (FO[<]) with a bounded number of quantifier alternations. This resolves a long-standing open question in theoretical computer science, with implications for understanding the expressive power of logical formalisms for describing properties of sequences.

What Problem Does This Paper Address?

First-order logic (FO[<]) is a powerful tool for describing properties of strings (words). However, the complexity of the properties that can be expressed is often related to how quantifiers (like "for all" and "there exists") alternate in the formula. The "alternation hierarchy" categorizes languages based on the minimum number of such alternations needed to define them. A key question, open since 1971, was whether we can algorithmically determine, for any given regular language, which level of this hierarchy it belongs to. This is equivalent to asking if we can decide, for any regular language, whether it can be expressed by a FO[<] formula with at most i alternations for any given i.

Methods

The core of the paper's contribution lies in a novel technique involving the "polynomial closure" of language classes and the concept of "V-separation."

  • Polynomial Closure: For a class of languages V, its polynomial closure, Pol(V), consists of finite unions of languages formed by concatenating languages from V with letters.
  • V-Separation: A language K separates L from L' if L is a subset of K and L' has no intersection with K. V-separation asks if there's a language K within a class V that separates L from L'. The decidability of V-separation for a class V is crucial, as it implies decidability of membership for languages in V.
  • Main Technical Result: The paper proves that if V-separation is decidable for a class V, then it's also decidable for its polynomial closure, Pol(V). This inductive step is key to building up decidability for higher levels of the alternation hierarchy.
  • Algebraic Approach: The proof heavily relies on algebraic structures like monoids and semigroups, and the concept of "profinite words" to handle infinite sequences of words. They introduce a sophisticated construction involving "relational expansions" of monoids to bridge the gap between decidability for V and Pol(V).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Logic and Language Theory: The paper elegantly connects the expressive power of logical formulas (alternation hierarchy) with algebraic structures (monoids) and language-theoretic concepts (polynomial closure, separation).
  • Inductive Decidability: The core insight is that decidability of a property for a base class of languages can be "lifted" to more complex classes (like polynomial closures) through a carefully constructed inductive argument.
  • The Power of Polynomial Closure: The paper demonstrates that the polynomial closure operation, while seemingly simple, plays a critical role in building up the complexity of definable languages and that its separation problem is decidable if the base class's separation problem is.
  • Relational Expansions: The novel construction of "relational expansions" provides a powerful framework for reasoning about and computing properties related to polynomial closure and V-pairs.

Key Results

  • Decidability of Alternation Hierarchy: The paper proves that for any i, it is decidable whether a given regular language is definable by a first-order sentence with at most i quantifier alternations. This directly answers the question posed in 1971.
  • Algorithmic Complexity: The decidability is established constructively, providing an algorithm. The complexity of the algorithm for Pol(V)-separation is shown to be exponential in the complexity for V-separation. The authors conjecture a polynomial time complexity, which would be a significant improvement.
  • Corollaries: The results have direct implications for the decidability of membership in levels of the dot-depth hierarchy and the group-based concatenation hierarchy.

Limitations and Future Work

  • Complexity Blow-up: The current algorithm for Pol(V)-separation has an exponential time complexity blow-up. The authors conjecture that this can be reduced to polynomial time, which would be a significant algorithmic improvement.
  • Boolean Closure: The paper leaves open the question of decidability for the Boolean closure of alternation hierarchy levels. This is a natural extension and was part of the original "dot-depth" question.
  • FO with Additional Predicates: The authors suggest exploring decidability for first-order logic with additional predicates beyond just '<', such as '+1' or modulo operations, which are relevant for defining a broader range of languages.

Summary updated

BibTeX
@misc{cadilhac2025alternation,
  author = {Michaël Cadilhac},
  title = {{The Alternation Hierarchy of First-Order Logic on Words is Decidable}},
  year = {2025},
  eprint = {2501.14899},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.14899},
}
Figure