<p>It is known that every regular language can be defined by a purely existential MSO formula, so the quantifier rank hierarchy of MSO on words has only two levels <span class="math-container">$0$</span> and <span class="math-container">$1$</span>. A proof of this can, e.g., be found in the book <a href="https://doi.org/10.1007/978-1-4612-0289-9" rel="nofollow noreferrer">&quot;Finite Automata, Formal Logic, and Circuit Complexity&quot;</a> by Howard Straubing.
On the other hand, it is an open problem whether the generalized star-height hierarchy is infinite, or even whether there exists regular languages that require generalized star-height greater than <span class="math-container">$1$</span>. So there does not seem to be a known correspondence between the two hierarchies.</p>

CC BY-SA 4.0
2024-09-16T11:32:58.977Z
Thanks, I also found the collapse being mentioned in the introduction of [this](https://doi.org/10.1109/LICS.1997.614951) work. To be precise, I think the correspondence could still hold right? In that case there would be no languages of star-height 2. However, this does answers that it is probably not known in literature.
Janmar
CC BY-SA 4.0
2024-09-16T11:39:59.030Z
You're right, I edited the answer accordingly
Jan Johannsen
CC BY-SA 4.0
2024-09-16T11:11:51.557Z
2024-09-16T11:39:10.547Z
2024-09-16T11:39:10.547Z
Jan Johannsen
<p>The generalized star height of a regular language is defined as the maximal number of nested Kleene-stars in a regular expression (with union, concatenation, complement, and Kleene-stars) that recognizes the language.</p>
<p>The Schützenberger theorem famously states that for a regular language <span class="math-container">$L$</span>, the following conditions are equivalent:</p>
<ol>
<li><span class="math-container">$L$</span> has star height <span class="math-container">$0$</span> (i.e. regular expressions without Kleene-star),</li>
<li><span class="math-container">$L$</span> is recognized by a first order logic (FO) formula, and</li>
<li>the syntactic monoid of <span class="math-container">$L$</span> is aperiodic.</li>
</ol>
<p>Where point (2) is attributed to McNaughton-Papert.
Is there a generalization of this equivalence between (1) and (2) for languages with bounded star height and a specific fragment of MSO? It seems intuitive that this would correspond to MSO formulas with a bounded number of nested monadic quantifiers, but I have not been able to find such correspondences in the literature.</p>

<fl.formal-languages><regular-language><first-order-logic>
Bounded Star Height and corresponding fragments of MSO
Janmar
# Bounded Star Height and corresponding fragments of MSO

(Asked by: username_0 on 2024-09-16)

The generalized star height of a regular language is defined as the maximal number of nested Kleene-stars in a regular expression (with union, concatenation, complement, and Kleene-stars) that recognizes the language.

The Schützenberger theorem famously states that for a regular language $L$, the following conditions are equivalent:

1. $L$ has star height $0$ (i.e. regular expressions without Kleene-star),
2. $L$ is recognized by a first order logic (FO) formula, and
3. the syntactic monoid of $L$ is aperiodic.

Where point (2) is attributed to McNaughton-Papert.
Is there a generalization of this equivalence between (1) and (2) for languages with bounded star height and a specific fragment of MSO? It seems intuitive that this would correspond to MSO formulas with a bounded number of nested monadic quantifiers, but I have not been able to find such correspondences in the literature.

**Tags:** fl.formal-languages, regular-language, first-order-logic

---

## 1 answers

### Answer by username_1 on 2024-09-16. Score: 5 | Accepted answer

It is known that every regular language can be defined by a purely existential MSO formula, so the quantifier rank hierarchy of MSO on words has only two levels $0$ and $1$. A proof of this can, e.g., be found in the book ["Finite Automata, Formal Logic, and Circuit Complexity"](https://doi.org/10.1007/978-1-4612-0289-9) by Howard Straubing.
On the other hand, it is an open problem whether the generalized star-height hierarchy is infinite, or even whether there exists regular languages that require generalized star-height greater than $1$. So there does not seem to be a known correspondence between the two hierarchies.

> **Comments:**
> **username_0**: Thanks, I also found the collapse being mentioned in the introduction of [this](https://doi.org/10.1109/LICS.1997.614951) work. To be precise, I think the correspondence could still hold right? In that case there would be no languages of star-height 2. However, this does answers that it is probably not known in literature.  
> **username_1**: You're right, I edited the answer accordingly  

---

