Constructible Words Characterize Rational Languages of Words Indexed by Scattered Linear Orderings

Jul 16, 2026

Automata on linear orderings generalize finite-, infinite-, and transfinite-word automata by treating a word as a function from a linear ordering to a finite alphabet. To make reasoning feasible, constructible words are introduced as objects with a finite canonical notation produced by finitely many simple operators. The paper proves that a rational language of words indexed by scattered (countable and uncountable) linear orderings is fully characterized by its constructible words. The argument uses a semigroup theorem of Colcombet and is intended to support further theoretical developments.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages20

Reading Time50 min

Introduction

Constructible Words and Automata on Scattered Linear Orderings

arXiv :2607 .0 1858v 1 [ cs .FL] 2 Jul 2026 Constructible Words Characterize Rational Languages of Words Indexed by Scattered Linear Orderings Thomas Braipson \# University of Liège, Montefiore Institute B28 Allée de la découverte 9 4000 Liège, Belgium Tom Clara \# University of Liège, Montefiore Institute B28 Allée de la découverte 9 4000 Liège, Belgium ~~ Abstract ~~ Automata on linear orderings are finite-state automata introduced by Bruyère and Carton as a broad generalization of finite, infinite and transfinite-word automata. In this context, a word is defined asa function from a linear ordering to a finite alphabet. This general definition can make automata on linear orderings difficult to reason about. In this work, we introduce constructible words asan intuitive way of tackling this difficulty. These words can be obtained by a finite number of applications of simple operators and thus admit a finite notation. We show that a rational language of words indexed by scattered (countable and uncountable) linear orderings is characterized by its constructible words. Our proof of this result relies on an interesting theorem of semigroup theory due to Colcombet. We expect this property to be useful in future theoretical developments about automata on scattered linear orderings. 2012 ACM Subject Classification Theory of computation → Automata over infinite objects Keywords and phrases Automata on linear orderings, Rational languages, Ultimately periodic words, Constructible Words, Complementation, Algebraic properties of automata, Semigroups Funding This work is partially supported by the FNRS-DFG PDR Weave (SMT-ART) grant 40019202. Thomas Braipson: has been granted with a FRIA grant. Tom Clara: is a Research Fellow of the F.R.S.-FNRS. Acknowledgements The authors wish to thank Olivier Carton for discussing with them and advertising Colcombet’s theorem. They also wish to thank the anonymous reviewers for their comments and ideas to go beyond this paper. 1 Introduction Automata on linear orderings [5, 3 , 4] were introduced by Bruyère and Carton and consist of a broad and elegant generalization of finite-word automata, infinite-word automata [23], automata on bi-infinite words [16] and transfinite words [24, 11] . In the context of automata on linear orderings, a word is defined as a function from any linear (i.e., total) ordering to a finite alphabet. This flexible definition generalizes the previously mentioned common notions of words. Reasoning about automata on linear orderings (for instance, showing that two automata accept exactly the same words) can be tedious, since some complex words do not admit a natural mental representation. In this work, we introduce a theoretical tool that addresses this problem. We first define a constructible word as a word that admits a canonical, finite representation. We then prove that automata on scattered (countable and uncountable) linear orderings that accept the same constructible words are equivalent. Stated differently, rational languages of words indexed by scattered linear orderings are characterized by their constructible words. We expect this result to be useful in further developments. 2 Constructible Words and Automata on Scattered Linear Orderings Our work extends the characterization of ω-regular languages by ultimately periodic words [7, Fact 1] . A simple proof of this classical result relies on the closure of ω-regular languages under complementation [6] . However, rational languages of words indexed by scattered (countable and uncountable) linear orderings are not closed under complementation [18], hence our proof relies on different principles. Sketchily, our proof is based on the fact that some words cannot be distinguished by a finite-state automaton, which naturally induces an equivalence relation on words. This idea, already used by Büchi in [6], was then adapted by Carton and Rispal to prove that rational languages on finite-ran

FAQs

What are constructible words, and how are they defined in the paper?

Constructible words are defined as words that admit a canonical finite representation. They are obtained through finitely many applications of simple operators, enabling a finite notation.

What main characterization result does the paper establish?

For scattered linear orderings (both countable and uncountable), rational languages of words are characterized exactly by the set of their constructible words.

Why does the paper rely on semigroup theory, and whose theorem is used?

The proofs connect rational languages to semigroups and use a semigroup theorem by Colcombet. This theorem supports the infinite factorization-forest style argument needed for the characterization beyond countability.

Jul 16, 2026

Upload by Ava Thompson