<p>I know it is frowned upon to promote one's own results, but it turns out that I wrote an article precisely on this topic. So let me add a few characterizations of regular languages not already mentioned. The complete relevant references can be found in the bibliography of [1].</p>
<p>(1) <strong>Pumping Lemma</strong>. Several authors (Jaffe, Stanat and Weiss, Ehrenfeucht, Parikh and Rozenberg) have proposed extensions of the pumping lemma that characterise regular languages. The most powerful version was given by Varricchio:</p>
<p><strong>Theorem</strong>. A language <span class="math-container">$L$</span> is regular if and only if there is an integer <span class="math-container">$m &gt; 0$</span> such that, for
all words <span class="math-container">$x$</span>, <span class="math-container">$u_1, \ldots, u_m$</span> and <span class="math-container">$y$</span>, there exist <span class="math-container">$i, j$</span> with <span class="math-container">$1 \leq i &lt; j
 \leq m$</span> such that for all <span class="math-container">$k &gt;0$</span>,
<span class="math-container">$$
 xu_1 \dotsm u_{i-1}(u_i \dotsm u_j)^ku_{j+1} \dotsm u_my \in L \iff xu_1 \dotsm
 u_my \in L
$$</span></p>
<p>(2) <strong>Periodicity and permutation</strong>. A languages <span class="math-container">$L$</span> is <em>periodic</em> if, for any <span class="math-container">$u \in A^*$</span>, there exist integers <span class="math-container">$n, k &gt; 0$</span> such that, for all <span class="math-container">$x,y \in A^*$</span>, <span class="math-container">$xu^ny \in L \iff xu^{n+k}y \in L$</span>. It is <em><span class="math-container">$n$</span>-permutable</em> if, for any sequence <span class="math-container">$u_1, \ldots, u_n$</span> of <span class="math-container">$n$</span> words of <span class="math-container">$A^*$</span>, there exists a nontrivial permutation <span class="math-container">$\sigma$</span> of <span class="math-container">$\{1, \ldots, n\}$</span> such that, for all <span class="math-container">$x,y \in A^*$</span>, <span class="math-container">$xu_1 \dotsm u_ny \in L \iff xu_{\sigma(1)} \dotsm u_{\sigma(n)}y \in L$</span>. It is <em>permutable</em> if it is permutable for some <span class="math-container">$n &gt; 1$</span>.</p>
<p><strong>Theorem</strong> (Restivo and Reutenauer). A language is regular if and only if it is periodic and permutable.</p>
<p>(3) <strong>Iteration properties</strong>. The book of de Luca and Varricchio (1999) contains many results about iterations properties. Here is an example</p>
<p><strong>Theorem</strong>. A language <span class="math-container">$L$</span> is regular if and only if there exist integers <span class="math-container">$m$</span> and <span class="math-container">$s$</span> such that for any <span class="math-container">$z_1, \ldots, z_m \in A^*$</span>, there exist integers <span class="math-container">$h,k$</span> with <span class="math-container">$1 \leq h \leq k \leq m$</span>, such that for all <span class="math-container">$u, v \in A^*$</span>,
<span class="math-container">$$
uz_1 \dotsm z_mv \in L \iff uz_1 \dotsm z_{h-1}(z_h \dotsm z_k)^nz_{k+1} \dotsm z_mv \in L,
$$</span>
for all <span class="math-container">$n \geq s$</span>.</p>
<p>(4) <strong>Well quasi-orders</strong>.  A <em>quasi-order</em> (or <em>preorder</em>) on <span class="math-container">$A^*$</span> is a reflexive and transitive relation. A quasi-order <span class="math-container">$\leq$</span> is <em>stable</em> (or <em>monotone</em>) if, for all words <span class="math-container">$u, v, x, y$</span>, the condition <span class="math-container">$u \leq v$</span> implies <span class="math-container">$xuy \leq xvy$</span>. The connection with regular languages was first established by Ehrenfeucht, Haussler and Rozenberg (1983)</p>
<p><strong>Theorem</strong>. A language is regular if and only if it is an upper set with respect to some stable well quasi-order on <span class="math-container">$A^*$</span>.</p>
<p>(5) <strong>Formal series</strong></p>
<p><strong>Theorem</strong> (Restivo and Reutenauer 1984). A language is regular if and only if it and its complement are both supports of a rational series.</p>
<p>(6) <strong>Monadic second order logic</strong>. Characterizations using <span class="math-container">$\mathbf{MSO}$</span> were already mentioned, but let me add a consequence of Rabin's tree theorem. Consider the structure <span class="math-container">$(A^*, (S_a)_{a \in A})$</span>, where each <span class="math-container">$S_a$</span> is a binary
relation symbol, interpreted on <span class="math-container">$A^*$</span> as follows: <span class="math-container">$S_a(u,v)$</span> if and only if <span class="math-container">$v = ua$</span>. Let <span class="math-container">$\varphi(X)$</span> be a monadic second order formula with a free set-variable <span class="math-container">$X$</span>. We write <span class="math-container">$\exists! X\ \varphi(X)$</span> as a short hand for the formula <span class="math-container">$\exists X \Bigr(\varphi(X) \wedge \bigl(\forall Y\ [\varphi(Y) \rightarrow (Y = X)]\bigr)\Bigr)$</span>. A language <span class="math-container">$L$</span> is said to be definable in <span class="math-container">$\mathbf{MSO}[(S_a)_{a \in A}]$</span> if there exists a monadic second order formula <span class="math-container">$\varphi(X)$</span> such that <span class="math-container">$L$</span> satisfies <span class="math-container">$\exists! X\ \varphi(X)$</span>.</p>
<p><strong>Theorem</strong> (Rabin) A language of <span class="math-container">$A^*$</span> is regular if and only if it is definable in <span class="math-container">$\mathbf{MSO}[(S_a)_{a \in A}]$</span>.</p>
<p>(7) <strong>Second order logic</strong>.
Some fragments of (non monadic) second order logic --- in the signature <span class="math-container">$\{S, (\mathbf{a})_{a \in A}\}$</span> --- also capture the regular languages.</p>
<p>A <em>quantifier prefix</em> is any word on the alphabet <span class="math-container">$\{\exists, \forall\}$</span>. A <em>quantifier prefix class</em> is any set of quantifier prefixes. For any quantifier prefix <span class="math-container">$Q$</span>, let <span class="math-container">$\Sigma_0^1(Q)$</span> (resp. <span class="math-container">$\Pi_0^1(Q))$</span> be the set of all formulas of
the shape <span class="math-container">$\exists \mathbf{R}\ Q \varphi$</span> (resp. <span class="math-container">$\forall \mathbf{R}\ Q \varphi$</span>) where <span class="math-container">$\mathbf{R}$</span> is a list of relations and <span class="math-container">$\varphi$</span> is quantifier free. For every <span class="math-container">$k \geq 0$</span>, let <span class="math-container">$\Sigma_{k+1}^1(Q)$</span> (resp., <span class="math-container">$\Pi_{k+1}^1(Q)$</span>) be the set of all formulas of the form <span class="math-container">$\exists \mathbf{R}\ \Phi$</span> (resp. <span class="math-container">$\forall \mathbf{R}\ \Phi$</span>) where <span class="math-container">$\Phi$</span> is a <span class="math-container">$\Pi_k^1(Q)$</span> (resp. <span class="math-container">$\Sigma_k^1(Q)$</span>) formula. Finally, for every quantifier prefix class <span class="math-container">$\mathcal{Q}$</span>, let <span class="math-container">$\Sigma_k^1(\mathcal{Q}) = \bigcup_{Q \in \mathcal{Q}} \Sigma_k^1(Q)$</span>.</p>
<p>The fragment <span class="math-container">$\Sigma_1^1$</span>, also known as <em>existential second order</em> and frequently denoted by <span class="math-container">$\mathbf{ESO}$</span>, was first explored by Eiter, Gottlob and Gurevich (2000).</p>
<p><strong>Theorem</strong>. A syntactic fragment <span class="math-container">$\mathbf{ESO}(\mathcal{Q})$</span>
captures the regular languages if and only if <span class="math-container">$\mathcal{Q}$</span> is a quantifier prefix class contained in <span class="math-container">$\exists^*\forall(\forall \cup \exists^*)$</span> whose intersection with <span class="math-container">$\exists^*\forall\{\exists, \forall\}^+$</span> is nonempty.</p>
<p>The fragments <span class="math-container">$\Sigma_k^1(\mathcal{Q})$</span>, with <span class="math-container">$k \geq 2$</span>, were explored by Eiter, Gottlob and Schwentick (2002).</p>
<p><strong>Theorem</strong>. A syntactic fragment <span class="math-container">$\mathbf{ESO}(\mathcal{Q})$</span>
captures the regular languages if and only if <span class="math-container">$\mathcal{Q}$</span> is a quantifier prefix class contained in <span class="math-container">$\exists^*\forall(\forall \cup \exists^*)$</span> whose intersection with <span class="math-container">$\exists^*\forall\{\exists, \forall\}^+$</span> is nonempty.</p>
<p>Finally, the fragments <span class="math-container">$\Sigma_k^1(\mathcal{Q})$</span>, with <span class="math-container">$k \geq 2$</span>, were also explored by Eiter, Gottlob and Schwentick.</p>
<p><strong>Theorem</strong>. The fragments <span class="math-container">$\Sigma_2^1(\forall \forall)$</span> and <span class="math-container">$\Sigma_2^1(\forall \exists)$</span> capture the class of regular languages. Furthermore, for each <span class="math-container">$k \geq 0$</span>, the fragments <span class="math-container">$\Sigma_k^1(\forall)$</span> and <span class="math-container">$\Sigma_k^1(\exists)$</span> only define regular
languages.</p>
<p>For more information on this topic, the reader is invited to read the beautiful survey of Eiter, Gottlob and Schwentick (2010).</p>
<p>(8) Other examples can be found in [1], notably related to rewriting systems, but I would like to conclude with two beautiful results.</p>
<p><strong>Theorem</strong>. (Kunc 2005)
Let <span class="math-container">$K$</span> be an arbitrary language and let <span class="math-container">$L$</span> be a regular language. Then the greatest solution of the inequality <span class="math-container">$XK \subseteq LX$</span> is regular.</p>
<p>The situation is totally different for equations of the type <span class="math-container">$XK = LX$</span>. Indeed Kunc (2007) has shown that there exists a <em>finite</em> language <span class="math-container">$L$</span> such that the greatest solution of the equation <span class="math-container">$XL = LX$</span> is co-recursively enumerable complete, thus very far from being regular!</p>
<p>[1] J.-É. Pin, <a href="https://hal.science/hal-02949627v1/document" rel="noreferrer">How to prove that a language is regular or star-free?</a>, Proc. LATA 2020, LNCS 12038 (2020) 68-88</p>

CC BY-SA 4.0
2024-03-06T20:31:05.003Z
2024-03-06T20:31:05.003Z
J.-E. Pin
<p>Here are fun ones:</p>
<ul>
<li>computational interpretations of circular proofs for Kleene algebra in linear logic, see <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.45" rel="noreferrer">https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.45</a> (Theorem 24)</li>
<li>typed lambda terms processing Church encodings of words, see <a href="https://dl.acm.org/doi/10.5555/788018.788832" rel="noreferrer">https://dl.acm.org/doi/10.5555/788018.788832</a>, (Theorem 3.4)</li>
<li>clopen (i.e. closed and open) subsets of the free profinite monoid, see <a href="https://www.mimuw.edu.pl/%7Ebojan/20142015-2/alg/11-profinite-words/topology-on-profinite-words" rel="noreferrer">https://www.mimuw.edu.pl/~bojan/20142015-2/alg/11-profinite-words/topology-on-profinite-words</a></li>
</ul>

CC BY-SA 4.0
2024-03-06T22:25:33.357Z
Another circular proof paper, closely related to the one you mention, is "Substructural Proofs as Automata" https://doi.org/10.1007/978-3-319-47958-3_1
Lê Thành Dũng 'Tito' Nguyễn
CC BY-SA 4.0
2024-02-04T23:35:24.090Z
2024-02-04T23:44:57.613Z
2024-02-04T23:44:57.613Z
Denis
<p>I think this one may fit the bill:</p>
<hr />
<p>A language is regular if and only if its characteristic series is the support of an <span class="math-container">$\mathbb{N}$</span>-rational series.</p>
<hr />
<p><strong>Definitions.</strong> Let <span class="math-container">$\Sigma$</span> be an alphabet and <span class="math-container">$\mathbb{K}$</span> be a <a href="https://en.wikipedia.org/wiki/Semiring#:%7E:text=In%20abstract%20algebra%2C%20a%20semiring,must%20have%20an%20additive%20inverse." rel="nofollow noreferrer">semiring</a>. A formal series <span class="math-container">$S$</span> is a function <span class="math-container">$S : \Sigma^* \to \mathbb{K}$</span>. A coefficient of a string <span class="math-container">$s$</span>, denoted <span class="math-container">$\kappa_s$</span>, in <span class="math-container">$S$</span> is the image of the string <span class="math-container">$s$</span> under <span class="math-container">$S$</span>. Indeed, <span class="math-container">$S = \sum_{s \in \Sigma^*} \kappa_s s$</span>. The language consisting of set of strings with nonzero coefficients is called the <em>support</em> <span class="math-container">$\mathrm{supp}(S)$</span> of a series. The set of all formal series over <span class="math-container">$\Sigma^*$</span> taking coefficients in <span class="math-container">$\mathbb{K}$</span> is denoted by <span class="math-container">$\mathbb{K}\langle \Sigma^* \rangle$</span>. A formal series <span class="math-container">$S \in \mathbb{K}\langle \Sigma^* \rangle$</span> is called <span class="math-container">$\mathbb{K}$</span> <em>proper</em> if the coefficient of the neutral element of <span class="math-container">$\Sigma^*$</span> vanishes, i.e. if <span class="math-container">$\kappa_{\mathrm e} = 0$</span>. A matrix over <span class="math-container">$\mathbb{K}\langle \Sigma^* \rangle$</span> is said to be <span class="math-container">$\mathbb{K}$</span>-rational if all of its entries are proper. A formal series <span class="math-container">$S \in \mathbb{K}\langle \Sigma^* \rangle$</span> is said to be <em>recognisable</em> if its coefficients can all be written as
<span class="math-container">$$\kappa_s = \alpha \cdot \mu(s) \cdot \beta,$$</span>
where for some <span class="math-container">$n \geq 1$</span> we have <span class="math-container">$\alpha \in \mathbb{K}^{1,n}$</span> and <span class="math-container">$\beta \in \mathbb{K}^{n, 1}$</span>, and the mapping <span class="math-container">$\mu: \Sigma^* \to \mathbb{K}^{n, n}$</span> is a multiplicative homomorphism of monoids. The <em>characteristic series</em> <span class="math-container">$\mathrm{char}(L)$</span> of a language <span class="math-container">$L \subseteq \Sigma^*$</span> is the series <span class="math-container">$S \in \mathbb{B}\langle \Sigma^* \rangle$</span> whose coefficients equal either <span class="math-container">$0$</span> or <span class="math-container">$1$</span> where
<span class="math-container">$$\kappa_s = \begin{cases}1 &amp;\text{if $s \in L$}\\0 &amp;\text{if $s \notin L$,}\end{cases}$$</span>
for all <span class="math-container">$s \in \Sigma^*$</span>.</p>
<hr />
<p>One can find most of these terms and other results in <a href="https://maa.org/sites/default/files/pdf/upload_library/22/Ford/IvanNiven.pdf" rel="nofollow noreferrer">[Niv69]</a>, <a href="https://inserm.hal.science/CV_LIGM/hal-00619791v1" rel="nofollow noreferrer">[BR88]</a>, and, especially, <a href="https://link.springer.com/book/10.1007/978-1-4612-6264-0" rel="nofollow noreferrer">[SS78]</a>.</p>

CC BY-SA 4.0
2024-02-23T01:01:54.773Z
Thanks! Are these mappings $\mu$ at all related to what Conway calls "Event Transition Matrices"? i.e. matrices $M$ such that $M_{i,j}$ is the sum of input characters taking state $i$ to state $j$, and so $M^n_{i,j}$ is the sum (with multiplicity) of words of length $n$ taking state $i$ to state $j$ and thus $M^*_{i,j} = \sum_n M^n_{i,j}$ is the sum (with multiplicity) of all words taking state $i$ to state $j$?
TomKern
CC BY-SA 4.0
2024-02-04T12:01:03.630Z
2024-02-04T12:01:03.630Z
Ekene E.
<p>The following restrictions on Turing machines force them to recognize only regular languages:</p>
<ul>
<li>space complexity <span class="math-container">$o(\log \log n)$</span> <a href="https://doi.org/10.1109/FOCS.1965.11" rel="noreferrer">https://doi.org/10.1109/FOCS.1965.11</a></li>
<li>single-tape with time complexity <span class="math-container">$o(\log n)$</span> <a href="https://doi.org/10.1016/0304-3975(85)90165-3" rel="noreferrer">https://doi.org/10.1016/0304-3975(85)90165-3</a></li>
</ul>

CC BY-SA 4.0
2024-03-06T22:32:18.587Z
2024-03-06T22:32:18.587Z
Lê Thành Dũng 'Tito' Nguyễn
<p>A language is regular if and only if it is linearly separable by the DFA kernel, defined here:</p>
<p><a href="https://cstheory.stackexchange.com/questions/7512/how-many-dfas-accept-two-given-strings">How many DFAs accept two given strings?</a></p>
<p>This is Theorem 11 in
<a href="https://www.sciencedirect.com/science/article/pii/S0304397508004581" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/S0304397508004581</a></p>

CC BY-SA 4.0
2024-02-04T10:10:32.527Z
2024-02-04T10:10:32.527Z
Aryeh
<p>I've been collecting equivalent characterizations of the regular languages. Does anyone know of any I haven't yet found?</p>
<p>Wikipedia has a bunch: <a href="https://en.wikipedia.org/wiki/Regular_language#Equivalent_formalisms" rel="noreferrer">https://en.wikipedia.org/wiki/Regular_language#Equivalent_formalisms</a></p>
<ul>
<li>it is the language of a regular expression (by the above definition)</li>
<li>it is the language accepted by a nondeterministic finite automaton (NFA)</li>
<li>it is the language accepted by a deterministic finite automaton (DFA)</li>
<li>it can be generated by a regular grammar</li>
<li>it is the language accepted by an alternating finite automaton</li>
<li>it is the language accepted by a two-way finite automaton</li>
<li>it can be generated by a prefix grammar</li>
<li>it can be accepted by a read-only Turing machine</li>
<li>it can be defined in monadic second-order logic (Büchi–Elgot–Trakhtenbrot theorem)</li>
<li>it is recognized by some finite syntactic monoid <span class="math-container">$M$</span>, meaning it is the preimage <span class="math-container">$\{w \in \Sigma^* | f(w) \in S\}$</span> of a subset <span class="math-container">$S$</span> of a finite monoid <span class="math-container">$M$</span> under a monoid homomorphism <span class="math-container">$f: \Sigma^* \to M$</span> from the free monoid on its alphabet</li>
<li>the number of equivalence classes of its syntactic congruence is finite. (This number equals the number of states of the minimal deterministic finite automaton accepting L.)</li>
</ul>
<p>And I'm aware of a few more:</p>
<ul>
<li>Language accepted by an NFA with edges labeled by regular expressions (traversing an edge consumes a sequence of characters matching that regular expression) [These are &quot;nondeterministic generalized finite automata&quot; in &quot;Automata Theory and its Applications&quot;, Khoussainov &amp; Nerode]</li>
<li>Languages generated by languages of the form <span class="math-container">$ A^* $</span> and <span class="math-container">$A^* cd A^*$</span> (<span class="math-container">$A$</span> a set of characters, <span class="math-container">$c,d$</span> arbitrary characters) under Boolean operations and characterwise maps [This is Theorem 3.6 from &quot;Decision Problems of Finite Automata Design and Related Arithmetics&quot; by Elgot]</li>
<li>First-order describable subsets of Büchi Arithmetic under a suitable translation</li>
<li>First-order describable subsets of the words on a finite alphabet with predicates for prefix and equal length, and unary operations tack-an-<span class="math-container">$a$</span>-onto-the-end for each character <span class="math-container">$a$</span>.</li>
</ul>
<p>I imagine there are more I don't know about through connections with other branches of mathematics, or possibly through the connection between <span class="math-container">$\frac{1}{1-x} = 1+x+x^2+x^3+\cdots$</span> and <span class="math-container">$A^* = \epsilon + A + AA + AAA + \cdots$</span>.</p>

CC BY-SA 4.0
2024-02-04T03:16:33.563Z
Single-tape TMs in time o(n log n) (important that this is little-oh).
Joshua Grochow
CC BY-SA 4.0
2024-02-05T03:23:51.047Z
Does ["circular" unification](https://dl.acm.org/doi/pdf/10.1145/800017.800528) apply here?
ShyPerson
CC BY-SA 4.0
2024-08-26T09:48:33.617Z
a small typo: "it is recognized by some finite syntactic monoid $M$" -> "it is recognized by some finite monoid $M$". Since $M$ can be any finite monoid, not necessarily the syntactic monoid of the language, although indeed the syntactic monoid will be finite just in case the language is regular (this is another equivalent characterization of regularity, essentially a rephrasing of "the number of equivalence classes of its syntactic congruence is finite").
Noam Zeilberger
<fl.formal-languages><automata-theory><big-list><regular-language>
Obscure characterizations of the regular languages
TomKern
# Obscure characterizations of the regular languages

(Asked by: username_0 on 2024-02-03)

I've been collecting equivalent characterizations of the regular languages. Does anyone know of any I haven't yet found?

Wikipedia has a bunch: <https://en.wikipedia.org/wiki/Regular_language#Equivalent_formalisms>

* it is the language of a regular expression (by the above definition)
* it is the language accepted by a nondeterministic finite automaton (NFA)
* it is the language accepted by a deterministic finite automaton (DFA)
* it can be generated by a regular grammar
* it is the language accepted by an alternating finite automaton
* it is the language accepted by a two-way finite automaton
* it can be generated by a prefix grammar
* it can be accepted by a read-only Turing machine
* it can be defined in monadic second-order logic (Büchi–Elgot–Trakhtenbrot theorem)
* it is recognized by some finite syntactic monoid $M$, meaning it is the preimage $\{w \in \Sigma^\* | f(w) \in S\}$ of a subset $S$ of a finite monoid $M$ under a monoid homomorphism $f: \Sigma^\* \to M$ from the free monoid on its alphabet
* the number of equivalence classes of its syntactic congruence is finite. (This number equals the number of states of the minimal deterministic finite automaton accepting L.)

And I'm aware of a few more:

* Language accepted by an NFA with edges labeled by regular expressions (traversing an edge consumes a sequence of characters matching that regular expression) [These are "nondeterministic generalized finite automata" in "Automata Theory and its Applications", Khoussainov & Nerode]
* Languages generated by languages of the form $ A^\* $ and $A^\* cd A^\*$ ($A$ a set of characters, $c,d$ arbitrary characters) under Boolean operations and characterwise maps [This is Theorem 3.6 from "Decision Problems of Finite Automata Design and Related Arithmetics" by Elgot]
* First-order describable subsets of Büchi Arithmetic under a suitable translation
* First-order describable subsets of the words on a finite alphabet with predicates for prefix and equal length, and unary operations tack-an-$a$-onto-the-end for each character $a$.

I imagine there are more I don't know about through connections with other branches of mathematics, or possibly through the connection between $\frac{1}{1-x} = 1+x+x^2+x^3+\cdots$ and $A^\* = \epsilon + A + AA + AAA + \cdots$.

**Tags:** fl.formal-languages, automata-theory, big-list, regular-language
> **Comments:**
> **username_1**: Single-tape TMs in time o(n log n) (important that this is little-oh).  
> **username_2**: Does ["circular" unification](https://dl.acm.org/doi/pdf/10.1145/800017.800528) apply here?  
> **username_3**: a small typo: "it is recognized by some finite syntactic monoid $M$" -> "it is recognized by some finite monoid $M$". Since $M$ can be any finite monoid, not necessarily the syntactic monoid of the language, although indeed the syntactic monoid will be finite just in case the language is regular (this is another equivalent characterization of regularity, essentially a rephrasing of "the number of equivalence classes of its syntactic congruence is finite").  

---

## 5 answers

### Answer by username_4 on 2024-03-06. Score: 12

I know it is frowned upon to promote one's own results, but it turns out that I wrote an article precisely on this topic. So let me add a few characterizations of regular languages not already mentioned. The complete relevant references can be found in the bibliography of [1].

(1) **Pumping Lemma**. Several authors (Jaffe, Stanat and Weiss, Ehrenfeucht, Parikh and Rozenberg) have proposed extensions of the pumping lemma that characterise regular languages. The most powerful version was given by Varricchio:

**Theorem**. A language $L$ is regular if and only if there is an integer $m > 0$ such that, for
all words $x$, $u\_1, \ldots, u\_m$ and $y$, there exist $i, j$ with $1 \leq i < j
\leq m$ such that for all $k >0$,
$$
xu\_1 \dotsm u\_{i-1}(u\_i \dotsm u\_j)^ku\_{j+1} \dotsm u\_my \in L \iff xu\_1 \dotsm
u\_my \in L
$$

(2) **Periodicity and permutation**. A languages $L$ is *periodic* if, for any $u \in A^\*$, there exist integers $n, k > 0$ such that, for all $x,y \in A^\*$, $xu^ny \in L \iff xu^{n+k}y \in L$. It is *$n$-permutable* if, for any sequence $u\_1, \ldots, u\_n$ of $n$ words of $A^\*$, there exists a nontrivial permutation $\sigma$ of $\{1, \ldots, n\}$ such that, for all $x,y \in A^\*$, $xu\_1 \dotsm u\_ny \in L \iff xu\_{\sigma(1)} \dotsm u\_{\sigma(n)}y \in L$. It is *permutable* if it is permutable for some $n > 1$.

**Theorem** (Restivo and Reutenauer). A language is regular if and only if it is periodic and permutable.

(3) **Iteration properties**. The book of de Luca and Varricchio (1999) contains many results about iterations properties. Here is an example

**Theorem**. A language $L$ is regular if and only if there exist integers $m$ and $s$ such that for any $z\_1, \ldots, z\_m \in A^\*$, there exist integers $h,k$ with $1 \leq h \leq k \leq m$, such that for all $u, v \in A^\*$,
$$
uz\_1 \dotsm z\_mv \in L \iff uz\_1 \dotsm z\_{h-1}(z\_h \dotsm z\_k)^nz\_{k+1} \dotsm z\_mv \in L,
$$
for all $n \geq s$.

(4) **Well quasi-orders**. A *quasi-order* (or *preorder*) on $A^\*$ is a reflexive and transitive relation. A quasi-order $\leq$ is *stable* (or *monotone*) if, for all words $u, v, x, y$, the condition $u \leq v$ implies $xuy \leq xvy$. The connection with regular languages was first established by Ehrenfeucht, Haussler and Rozenberg (1983)

**Theorem**. A language is regular if and only if it is an upper set with respect to some stable well quasi-order on $A^\*$.

(5) **Formal series**

**Theorem** (Restivo and Reutenauer 1984). A language is regular if and only if it and its complement are both supports of a rational series.

(6) **Monadic second order logic**. Characterizations using $\mathbf{MSO}$ were already mentioned, but let me add a consequence of Rabin's tree theorem. Consider the structure $(A^\*, (S\_a)\_{a \in A})$, where each $S\_a$ is a binary
relation symbol, interpreted on $A^\*$ as follows: $S\_a(u,v)$ if and only if $v = ua$. Let $\varphi(X)$ be a monadic second order formula with a free set-variable $X$. We write $\exists! X\ \varphi(X)$ as a short hand for the formula $\exists X \Bigr(\varphi(X) \wedge \bigl(\forall Y\ [\varphi(Y) \rightarrow (Y = X)]\bigr)\Bigr)$. A language $L$ is said to be definable in $\mathbf{MSO}[(S\_a)\_{a \in A}]$ if there exists a monadic second order formula $\varphi(X)$ such that $L$ satisfies $\exists! X\ \varphi(X)$.

**Theorem** (Rabin) A language of $A^\*$ is regular if and only if it is definable in $\mathbf{MSO}[(S\_a)\_{a \in A}]$.

(7) **Second order logic**.
Some fragments of (non monadic) second order logic --- in the signature $\{S, (\mathbf{a})\_{a \in A}\}$ --- also capture the regular languages.

A *quantifier prefix* is any word on the alphabet $\{\exists, \forall\}$. A *quantifier prefix class* is any set of quantifier prefixes. For any quantifier prefix $Q$, let $\Sigma\_0^1(Q)$ (resp. $\Pi\_0^1(Q))$ be the set of all formulas of
the shape $\exists \mathbf{R}\ Q \varphi$ (resp. $\forall \mathbf{R}\ Q \varphi$) where $\mathbf{R}$ is a list of relations and $\varphi$ is quantifier free. For every $k \geq 0$, let $\Sigma\_{k+1}^1(Q)$ (resp., $\Pi\_{k+1}^1(Q)$) be the set of all formulas of the form $\exists \mathbf{R}\ \Phi$ (resp. $\forall \mathbf{R}\ \Phi$) where $\Phi$ is a $\Pi\_k^1(Q)$ (resp. $\Sigma\_k^1(Q)$) formula. Finally, for every quantifier prefix class $\mathcal{Q}$, let $\Sigma\_k^1(\mathcal{Q}) = \bigcup\_{Q \in \mathcal{Q}} \Sigma\_k^1(Q)$.

The fragment $\Sigma\_1^1$, also known as *existential second order* and frequently denoted by $\mathbf{ESO}$, was first explored by Eiter, Gottlob and Gurevich (2000).

**Theorem**. A syntactic fragment $\mathbf{ESO}(\mathcal{Q})$
captures the regular languages if and only if $\mathcal{Q}$ is a quantifier prefix class contained in $\exists^\*\forall(\forall \cup \exists^\*)$ whose intersection with $\exists^\*\forall\{\exists, \forall\}^+$ is nonempty.

The fragments $\Sigma\_k^1(\mathcal{Q})$, with $k \geq 2$, were explored by Eiter, Gottlob and Schwentick (2002).

**Theorem**. A syntactic fragment $\mathbf{ESO}(\mathcal{Q})$
captures the regular languages if and only if $\mathcal{Q}$ is a quantifier prefix class contained in $\exists^\*\forall(\forall \cup \exists^\*)$ whose intersection with $\exists^\*\forall\{\exists, \forall\}^+$ is nonempty.

Finally, the fragments $\Sigma\_k^1(\mathcal{Q})$, with $k \geq 2$, were also explored by Eiter, Gottlob and Schwentick.

**Theorem**. The fragments $\Sigma\_2^1(\forall \forall)$ and $\Sigma\_2^1(\forall \exists)$ capture the class of regular languages. Furthermore, for each $k \geq 0$, the fragments $\Sigma\_k^1(\forall)$ and $\Sigma\_k^1(\exists)$ only define regular
languages.

For more information on this topic, the reader is invited to read the beautiful survey of Eiter, Gottlob and Schwentick (2010).

(8) Other examples can be found in [1], notably related to rewriting systems, but I would like to conclude with two beautiful results.

**Theorem**. (Kunc 2005)
Let $K$ be an arbitrary language and let $L$ be a regular language. Then the greatest solution of the inequality $XK \subseteq LX$ is regular.

The situation is totally different for equations of the type $XK = LX$. Indeed Kunc (2007) has shown that there exists a *finite* language $L$ such that the greatest solution of the equation $XL = LX$ is co-recursively enumerable complete, thus very far from being regular!

[1] J.-É. Pin, [How to prove that a language is regular or star-free?](https://hal.science/hal-02949627v1/document), Proc. LATA 2020, LNCS 12038 (2020) 68-88


---

### Answer by username_5 on 2024-02-04. Score: 5

Here are fun ones:

* computational interpretations of circular proofs for Kleene algebra in linear logic, see <https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.45> (Theorem 24)
* typed lambda terms processing Church encodings of words, see <https://dl.acm.org/doi/10.5555/788018.788832>, (Theorem 3.4)
* clopen (i.e. closed and open) subsets of the free profinite monoid, see [https://www.mimuw.edu.pl/~bojan/20142015-2/alg/11-profinite-words/topology-on-profinite-words](https://www.mimuw.edu.pl/%7Ebojan/20142015-2/alg/11-profinite-words/topology-on-profinite-words)

> **Comments:**
> **username_6**: Another circular proof paper, closely related to the one you mention, is "Substructural Proofs as Automata" https://doi.org/10.1007/978-3-319-47958-3_1  

---

### Answer by username_6 on 2024-03-06. Score: 5

The following restrictions on Turing machines force them to recognize only regular languages:

* space complexity $o(\log \log n)$ <https://doi.org/10.1109/FOCS.1965.11>
* single-tape with time complexity $o(\log n)$ <https://doi.org/10.1016/0304-3975(85)90165-3>


---

### Answer by username_7 on 2024-02-04. Score: 4

I think this one may fit the bill:

---

A language is regular if and only if its characteristic series is the support of an $\mathbb{N}$-rational series.

---

**Definitions.** Let $\Sigma$ be an alphabet and $\mathbb{K}$ be a [semiring](https://en.wikipedia.org/wiki/Semiring#:%7E:text=In%20abstract%20algebra%2C%20a%20semiring,must%20have%20an%20additive%20inverse.). A formal series $S$ is a function $S : \Sigma^\* \to \mathbb{K}$. A coefficient of a string $s$, denoted $\kappa\_s$, in $S$ is the image of the string $s$ under $S$. Indeed, $S = \sum\_{s \in \Sigma^\*} \kappa\_s s$. The language consisting of set of strings with nonzero coefficients is called the *support* $\mathrm{supp}(S)$ of a series. The set of all formal series over $\Sigma^\*$ taking coefficients in $\mathbb{K}$ is denoted by $\mathbb{K}\langle \Sigma^\* \rangle$. A formal series $S \in \mathbb{K}\langle \Sigma^\* \rangle$ is called $\mathbb{K}$ *proper* if the coefficient of the neutral element of $\Sigma^\*$ vanishes, i.e. if $\kappa\_{\mathrm e} = 0$. A matrix over $\mathbb{K}\langle \Sigma^\* \rangle$ is said to be $\mathbb{K}$-rational if all of its entries are proper. A formal series $S \in \mathbb{K}\langle \Sigma^\* \rangle$ is said to be *recognisable* if its coefficients can all be written as
$$\kappa\_s = \alpha \cdot \mu(s) \cdot \beta,$$
where for some $n \geq 1$ we have $\alpha \in \mathbb{K}^{1,n}$ and $\beta \in \mathbb{K}^{n, 1}$, and the mapping $\mu: \Sigma^\* \to \mathbb{K}^{n, n}$ is a multiplicative homomorphism of monoids. The *characteristic series* $\mathrm{char}(L)$ of a language $L \subseteq \Sigma^\*$ is the series $S \in \mathbb{B}\langle \Sigma^\* \rangle$ whose coefficients equal either $0$ or $1$ where
$$\kappa\_s = \begin{cases}1 &\text{if $s \in L$}\\0 &\text{if $s \notin L$,}\end{cases}$$
for all $s \in \Sigma^\*$.

---

One can find most of these terms and other results in [[Niv69]](https://maa.org/sites/default/files/pdf/upload_library/22/Ford/IvanNiven.pdf), [[BR88]](https://inserm.hal.science/CV_LIGM/hal-00619791v1), and, especially, [[SS78]](https://link.springer.com/book/10.1007/978-1-4612-6264-0).

> **Comments:**
> **username_0**: Thanks! Are these mappings $\mu$ at all related to what Conway calls "Event Transition Matrices"? i.e. matrices $M$ such that $M_{i,j}$ is the sum of input characters taking state $i$ to state $j$, and so $M^n_{i,j}$ is the sum (with multiplicity) of words of length $n$ taking state $i$ to state $j$ and thus $M^*_{i,j} = \sum_n M^n_{i,j}$ is the sum (with multiplicity) of all words taking state $i$ to state $j$?  

---

### Answer by username_8 on 2024-02-04. Score: 3

A language is regular if and only if it is linearly separable by the DFA kernel, defined here:

[How many DFAs accept two given strings?](https://cstheory.stackexchange.com/questions/7512/how-many-dfas-accept-two-given-strings)

This is Theorem 11 in
<https://www.sciencedirect.com/science/article/pii/S0304397508004581>


---

