# LTL is a star-free language but it can describe $a^*b^\omega$. Contradiction?

Does the statement "LTL is a star-free language"(from wiki) mean that the expressiveness power of LTL is equivalent to that of star-free languages? Then why can you describe in LTL the following language with a star $a^*b^\omega$? $$\mathbf{G}(a \implies a\mathbf{U}b) \land G(b \implies \mathbf{X}b)$$ So, what does "LTL is star-free language" mean? Can you give an example of regular language with star which cannot be expressed in LTL? (not an example of LTL < NBA, but an example of LTL < regular language with star)

-
Star-free languages allow all Boolean operators, including concatenation; that makes it possible to describe some languages that are more naturally described using the star. –  Brian M. Scott Mar 5 '12 at 13:29
@BrianM.Scott sorry, didn't get your point: LTL also allows Boolean operators including concatenation and complementation.. –  Ayrat Mar 5 '12 at 13:52
The point is that although you’ve used the star to describe $a^*b^\omega$, that doesn’t mean that this language is not star-free. You should try to find a different description of it that doesn’t use the star; I’ve not checked carefully, but I suspect that you can use the same idea that’s used in the example in the Wikipedia article to which I linked. –  Brian M. Scott Mar 5 '12 at 14:04
I have found this expository paper that might be of interest. It appears that $(aa)^*$ is not a star-free language. –  Arthur Fischer Mar 5 '12 at 15:36
You misquote Wikipedia. The phrase you use would suggest that the language of LTL formula was star-free, which does not match your question at all. –  Raphael Apr 11 '12 at 10:27

## 2 Answers

Short answer: $a^*b^{\omega}$ describes a star-free language.

Longer answer:

In order to show that let's consider two definitions of a regular star-free language :

• Language has a maximum star height of 0.
• Language is in the class of star-free languages, which is defined as follows: it's the smallest subset of $\Sigma^{\omega}$ which contains $\Sigma^{\omega}$, all singletons $\{x\}$, $x \in \Sigma$, and which is closed under finite union, concatenation and complementation.

It's possible to see that those two definitions are equivalent. We can also note that all finite languages are star-free.

An $\omega$-regular language is called $\omega$-star-free if it's a finite union of languages of type $XY^{\omega}$, where $X$ and $Y^+$ are star-free.

Now, $L = a^*$ can be described as $\Sigma^* \setminus (\Sigma^* (\Sigma \setminus a) \Sigma^*)$, so $L$ is a star-free language. Since $L' = a^* b^{\omega}$ can be written as concatenation in the form of $XY^{\omega}$ where $X = L$ and $Y = \{b\}$ (it's easy to show that $Y^+$ is star-free) we can conclude that $L'$ is star-free.

For more information (and equivalent definitions) I can refer you to the following papers: First-order definable languages, On the Expressive Power of Temporal Logic, On the expressive power of temporal logic for infinite words

-
Quite complicated(didn't actually get details), I think this is easier(and likely the same): omega-star free language is the lang that can be represented as $XY^\omega$, where $X$, $Y$ are star-free regular languages(can be expressed with $\neg$, $\cup$, $\emptyset$, {single letter of $\Sigma$}). Since $a^* = \neg(\Sigma^*b\Sigma^*)$, where $\Sigma^*=\neg\emptyset$, is star-free regular, and single letter $b$ is also star-free regular => $a^*b^{\omega}$ is $\omega$-star-free regular. Thanks for refs and inspiring. –  Ayrat Apr 15 '12 at 20:10

Indeed, the language $a^*b^\omega$ is star-free, and it can be equivalently captured by $L_1L_2$, where $$L_1=\Sigma^*b\backslash(\Sigma^*(\Sigma\backslash a)\Sigma^*b)$$ and $$L_2=\Sigma^\omega\backslash(\Sigma^*(\Sigma\backslash b)\Sigma^\omega).$$ In the above, $L_1$ and $L_2$ are respectively equal to $a^*b$ and $b^\omega$.

Note that for star-free expressions, Kleen-closure ($*$ and $\omega$) can only be applied to $\Sigma$ (the whole alphabet set).

B.T.W., you may simplify your LTL expression, and you can just use $a{\bf U}({\bf G}b)$.

-
why do you need $L1$ to represent $a^*b$ and not just $a^*$ as in the previous answer? seems to be no difference. Thanks for the note and $L2$! –  Ayrat Apr 19 '12 at 13:50