Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
1  
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
2  
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
1  
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
add comment

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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
add comment

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)$.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.