Regular expressions over countable words
Thomas Colcombet, A V Sreejith · 2025
Read Regular expressions over countable words by Thomas Colcombet, A V Sreejith (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-01039.txt.
Introduction
Thomas Colcombet and Sreejith investigate regular expressions for languages of countable words. Their 2025 arXiv paper extends classic regular language theory. Classic theory covers finite words and ties together automata, logic, and expressions. Countable words form a richer setting that needs new tools. The authors ask how much of the classic picture survives.
They introduce and study five classes of expressions. The classes range from marked star-free forms to scatter expressions. Each class matches a natural fragment of logic over countable words. Each also has a decidable algebraic description. The team gives a precise account using J-class structure. Together, the results complete a three-way match between logic, algebra, and expressions. Foundational results from the finite case thus carry over.
Catalog record
| CREATOR | Thomas Colcombet, A V Sreejith |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 200 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-01039
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Regular expressions over countable words Thomas Colcombet, A V Sreejith Abstract We investigate the expressive power of regular expressions for languages of countable words and establish their expressive equivalence with logical and algebraic characterizations. Our goal is to extend the classical theory of regular languages - defined over finite words and characterized by automata, monadic second-order logic, and regular expressions - to the setting of countable words. In this paper, we introduce and study five classes of expressions: marked star-free expressions , marked expressions , power-free expressions , scatter-free expressions , and scatter expressions . We show that these expression classes characterize natural fragments of logic over countable words and possess decidable algebraic characterizations. As part of our algebraic analysis, we provide a precise description of the relevant classes in terms of their 𝒥 \mathcal{J} -class structure. These results complete a triad of equivalences - between logic, algebra, and expressions - in this richer setting, thereby generalizing foundational results from classical formal language theory. IRIF [email protected] IIT [email protected] keywords countable words, expressions, logic, monoids † † runningauthor: Colcombet and Sreejith 1 Introduction and contributions This paper contributes to the theory of regular languages over countable words —that is, infinite words whose domains are countable linear orders, as opposed to \omega -words whose domains are isomorphic to the natural numbers. The foundational result in this direction is the decidability of satisfiability for monadic second-order logic (MSO) over countable words or chains [ 13 , 14 ] . Since then, the study of countable words has evolved into a rich theory that retain many foundational aspects of classical regular language theory over finite words. In particular, regular languages of finite words admit equivalent characterizations through several formal systems: automata (deterministic or nondeterministic), definability in MSO, recognizability by finite monoids, and regular expressions. Analogous equivalences have been established for languages of countable words; notably, MSO-definable languages over countable linear orders are known to coincide with those recognizable by \circledast -monoids [ 6 ] . A striking branch of research concerning regular languages of finite words is the algebraic characterization of sub-logics of MSO. The seminal result in this direction is the celebrated Schützenberger–McNaughton–Papert theorem, that states that a language is recognized by an aperiodic monoid if and only if it is definable by a star-free expression, which is itself equivalent to being definable in first-order logic (FO). This theorem initiated a deep line of research in formal language theory. In the setting of countable words, [ 7 ] establishes five correspondences between varieties of \circledast -monoids and natural sub-logics of MSO. These sub-logics arise by restricting set quantification in various ways: to singletons (yielding FO), to Dedekind cuts, to finite sets, and so on. This raises a natural question: can we identify natural classes of expressions that characterize these logics and algebraic varieties? To better understand the expressive power of the different classes of expressions we study, we now present a few illustrative examples. Example 1 . Let us consider the alphabet {\color[rgb]{0,0,0.7}\Sigma}=\{a,b\} and denote by \emptyset the empty language. The set of all countable words {\color[rgb]{0,0,0.7}\Sigma}^{{\color[rgb]{0,0,0.7}\circledast}} is then the complement of the empty language, written as \overline{\emptyset}{}{} . We present a few illustrative expressions: • The set of all words without any occurrence of the letter b is given by the marked star-free expression : {\color[rgb]{0,0,0.7}\mathtt{No(\mathnormal{b})}}{}{}\;::=\;\overline{{\color[rgb]{0,0,0.7}\Sigma}^{{\color[rgb]{0,0,0.7}\circledast}}b{\color[rgb]{0,0,0.7}\Sigma}^{{\color[rgb]{0,0,0.7}\circledast}}}{}{}, where the concatenation is marked by the letter b . • The set of all dense words over a is described by the following marked star-free expression : {\color[rgb]{0,0,0.7}\mathtt{Dense(\mathnormal{a})}}{}{}\;::=\;\overline{{\color[rgb]{0,0,0.7}\Sigma}^{{\color[rgb]{0,0,0.7}\circledast}}(aa){\color[rgb]{0,0,0.7}\Sigma}^{{\color[rgb]{0,0,0.7}\circledast}}}{}{}\ \bigcap\ {\color[rgb]{0,0,0.7}\mathtt{No(\mathnormal{b})}}{}{}\ \bigcap\ {\color[rgb]{0,0,0.7}\Sigma}^{{\color[rgb]{0,0,0.7}\circledast}}a{\color[rgb]{0,0,0.7}\Sigma}^{{\color[rgb]{0,0,0.7}\circledast}}, which expresses that there are no consecutive a ’s, no occurrence of b , and at least one occurrence of a . • The set of all words containing an odd number of b ’s separated by dense occurrences of a is given by the marked expression : {\color[rgb]{0,0,0.7}\mathtt{Odd(\mathnormal{b})\text{-}Dense(\mathnormal{a})}}{}{}\;::=\;{\big(b\ {\color[rgb]{0,0,0.7}\mathtt{Dense(\mathnormal{a})}}{}{}\ b\ {\color[rgb]{0,0,0.7}\mathtt{Dense(\mathnormal{a})}}{}{}\big)}^{{\color[rgb]{0,0,0.7}*}}{b}, where the Kleene star is marked by the leftmost letter b . • The property that the domain is well-founded (i.e., there is no infinite descending sequence) can be expressed by a power-free expression : {\color[rgb]{0,0,0.7}\mathtt{WellFounded}}{}{}\;::=\;\overline{{\color[rgb]{0,0,0.7}\Sigma}^{{\color[rgb]{0,0,0.7}\circledast}}\ \big(\overline{{\color[rgb]{0,0,0.7}\Sigma}{\color[rgb]{0,0,0.7}\Sigma}^{{\color[rgb]{0,0,0.7}\circledast}}\ +\ {\color[rgb]{0,0,0.7}\Sigma}^{{\color[rgb]{0,0,0.7}\circledast}}(a+b){\color[rgb]{0,0,0.7}\Sigma}^{{\color[rgb]{0,0,0.7}\circledast}}}{}{}\big)}{}{}. Similarly, a corresponding expression characterizes reverse well-foundedness . The domain is finite when it is both well-founded and reverse well-founded. • The property that the domain is scattered is captured by the scatter expression : {{\color[rgb]{0,0,0.7}\Sigma}}^{{\color[rgb]{0,0,0.7}sc}}, and the property that the occurrences of the letter b are scattered is given by: {\big({\color[rgb]{0,0,0.7}\mathtt{No(\mathnormal{b})}}{}{}\ b\ {\color[rgb]{0,0,0.7}\mathtt{No(\mathnormal{b})}}{}{}\big)}^{{\color[rgb]{0,0,0.7}sc}}. In this work, we complete the results of [ 7 ] by introducing five classes of regular expressions that match the five logical and algebraic characterizations. This leads to our main theorem, which establishes an expressive equivalence between logic (e.g., {\color[rgb]{0,0,0.7}\mathsf{fo}}{}{} , …), algebraic characterizations (e.g., varieties of o-monoids such as {\color[rgb]{0,0,0.7}\mathtt{Ap}} , …), and classes of regular expressions (e.g., marked expressions , …). A key technical contribution of our work is a detailed structural analysis of o-monoids. While {\color[rgb]{0,0,0.7}\mathcal{J}} -classes play a central role in classical algebraic characterizations of regular languages, their behavior in the setting of \circledast -monoids is more intricate. In this paper, we provide a framework for analyzing the J-classes and establish several new properties that are crucial for connecting the algebraic, logical and expression perspectives. In particular, our structure theorem for \circledast -monoids ( Theorem 12 ) reveals how idempotents interact in the countable setting. These properties provide for classifying \circledast -monoids in terms of their {\color[rgb]{0,0,0.7}\mathcal{J}} -classes and also the type of idempotents they contain. We then show that these natural classes turn out to be equivalent to interesting classes of expressions. Although we have not yet introduced all the necessary technical definitions, 1 1 1 Note that in the electronic version of this document, most technical terms are hyperlinked to their definitions. we state the main result here: Theorem 2 (main theorem) . Let \mathbf{M} be the syntactic \circledast -monoid of a language L\subseteq{\color[rgb]{0,0,0.7}\Sigma}^{{\color[rgb]{0,0,0.7}\circledast}} , then: 1. L is definable in {\color[rgb]{0,0,0.7}\mathsf{fo}} if and only if \mathbf{M} satisfies the equations {\color[rgb]{0,0,0.7}\mathtt{Ap}},{\color[rgb]{0,0,0.7}\mathtt{E{\text{\raisebox{1.22661pt}{\scalebox{.6}{${\subseteq}$}}}}GiE}}{}{},{\color[rgb]{0,0,0.7}\mathtt{ScE{\text{\raisebox{1.22661pt}{\scalebox{.6}{${\subseteq}$}}}}ShE}}{}{},{\color[rgb]{0,0,0.7}\mathtt{ShE{\text{\raisebox{1.22661pt}{\scalebox{.6}{${\subseteq}$}}}}SSE}}{}{} , if and only if all its regular {\color[rgb]{0,0,0.7}\mathcal{J}} -classes are shuffle simple regular , if and only if L is definable by marked star-free expressions . 2. L is definable in {\color[rgb]{0,0,0.7}\mathsf{fo}[}{\color[rgb]{0,0,0.7}\exists^{\mathsf{finite}}}{\color[rgb]{0,0,0.7}]}{}{} if and only if \mathbf{M} satisfies the equations {\color[rgb]{0,0,0.7}\mathtt{OE{\text{\raisebox{1.22661pt}{\scalebox{.6}{${\subseteq}$}}}}GiE}}{}{},{\color[rgb]{0,0,0.7}\mathtt{O^{*}E{\text{\raisebox{1.22661pt}{\scalebox{.6}{${\subseteq}$}}}}GiE}}{}{},{\color[rgb]{0,0,0.7}\mathtt{ScE{\text{\raisebox{1.22661pt}{\scalebox{.6}{${\subseteq}$}}}}ShE}}{}{},{\color[rgb]{0,0,0.7}\mathtt{ShE{\text{\raisebox{1.22661pt}{\scalebox{.6}{${\subseteq}$}}}}SSE}}{}{} , if and only if all its ordinal regular {\color[rgb]{0,0,0.7}\mathcal{J}} -classes and ordinal* regular {\color[rgb]{0,0,0.7}\mathcal{J}} -classes are shuffle simple regular , if and only if L is definable by marked expressions . 3. L is definable in {\color[rgb]{0,0,0.7}\mathsf{fo}[}{\color[rgb]{0,0,0.7}\exists^{\mathsf{cut}}}{\color[rgb]{0,0,0.7}]}{}{} if and only if \mathbf{M} satisfies the equations {\color[rgb]{0,0,0.7}\mathtt{Ap}},{\color[rgb]{0,0,0.7}\mathtt{ScE{\text{\raisebox{1.22661pt}{\scalebox{.6}{${\subseteq}$}}}}ShE}}{}{},{\color[rgb]{0,0,0.7}\mathtt{ShE{\text{\raisebox{1.22661pt}{\scalebox{.6}{${\subseteq}$}}}}SSE}}{}{} , if and only if it is aperiodic and all its scattered regular {\color[rgb]{0,0,0.7}\mathcal{J}} -classes are shuffle simple regular , if and only if L is definable by power-free expressions . 4. L is definable in {\color[rgb]{0,0,0.7}\mathsf{fo}[}{\color[rgb]{0,0,0.7}\exists^{\mathsf{finite}}},{\color[rgb]{0,0,0.7}\exists^{\mathsf{cut}}}{\color[rgb]{0,0,0.7}]}{}{} if and only if \mathbf{M} satisfies the equations {\color[rgb]{0,0,0.7}\mathtt{ScE{\text{\raisebox{1.22661pt}{\scalebox{.6}{${\subseteq}$}}}}ShE}}{}{},{\color[rgb]{0,0,0.7}\mathtt{ShE{\text{\raisebox{1.22661pt}{\scalebox{.6}{${\subseteq}$}}}}SSE}}{}{} , if and only if all its scattered regular {\color[rgb]{0,0,0.7}\mathcal{J}} -classes are shuffle simple regular , if and only if L is definable by scatter-free expressions . 5. L is definable in {\color[rgb]{0,0,0.7}\mathsf{fo}[}{\color[rgb]{0,0,0.7}\exists^{\mathsf{scattered}}}{\color[rgb]{0,0,0.7}]}{}{} if and only if \mathbf{M} satisfies the equations {\color[rgb]{0,0,0.7}\mathtt{ShE{\text{\raisebox{1.22661pt}{\scalebox{.6}{${\subseteq}$}}}}SSE}}{}{} , if and only if all its shuffle regular {\color[rgb]{0,0,0.7}\mathcal{J}} -classes are shuffle simple regular , if and only if L is definable in scatter expression . Furthermore, the problem of deciding whether