Let $L$ be a star-free language over finite alphabet $\Sigma$. A substitution will be a map $\sigma : \Sigma \to \mathcal{P}(\Sigma^*)$. It seems obvious that if $\sigma(a)$ is star-free for every $a \in \Sigma$, then $\sigma(L)$ will be star-free.
($\sigma(L) = \{ w_1 ... w_n | w_i \in \sigma(a_i) \land a_1 \ldots a_n \in L \}$) Take a star-free regular expression for $L$, and substitute star-free expressions for $L_i$ for each $a_i$ in that expression. The result will still be a star-free expression.

Now, my question is this: why is the following not a counterexample? $\Sigma = \{ 0, 1 \}$. $L = 1^*$ and $\sigma(1) = 0^* 1 0^* 1 0^*$. Both of these languages are star-free: $L = L( (\emptyset^c 0 \emptyset^c )^c )$ and similar tricks can be given to show that $\sigma(1)$ is star-free.

Now, the reason it seems like a counterexample: a word in $L$ contains only 1s. The substitution replaces each 1 with a word from a language whose words contain exactly 2 1s. So won't $\sigma(L)$ be the set of words with an even number of 1s, which is known to be non-star-free?

(Note: my proof suggestion of closure under substitution is a bit sketchy. The star-free expression for $1^*$ only has 0s in it. But I could then substitute the star-free expression for $\sigma(1)$ under a complement, no?)

  • 1
    $\begingroup$ Star-free expressions use Boolean operators. Isn't the problem that $\sigma(K\cap L) \neq \sigma(K) \cap \sigma(L)$? $\endgroup$ – Hendrik Jan Jun 8 '13 at 22:59

I do not understand your proof sketch. Where do you want to subtitute $\sigma(1)$ under a complement. The only thing substituable in the star-free expression for $1^*$ is $0$. But 0, or $\sigma(0)$ is an independent element in the substitution, it is in no way related to the complement of $\sigma(1)$. So this can in no way make a proof.

Actually, if there was such a closure property, it should be easy to find in the literature on star-free RE. But all closure results under substitution put constraints on the type of substitution, such as being length preserving, or being injective. See in particular papers by Jean-Eric Pin and others.

Also,Pin defines star-free substitutions on $\Sigma$ as requiring an additional property, namely that $(\sigma(\Sigma))^*$ is star-free. (though I did not check the precise role of this property)

It seems that you have just proved that star-free languages are not closed under star-free substitution as you define it.

This does not seem too surprising, since non injective substitution does not in general commute with complement or distribute with intersection.

Among other papers:
Jean-Eric Pin, H. Straubling, and D. Thérien. Some results on the generalized star-height problem. May 12 2002.

| cite | improve this answer | |
  • $\begingroup$ Thanks! I had trouble finding any mention of whether or not SF languages were closed under substitution except for passing reference in these slides that they were. That threw me for a loop since I thought my case was a counterexample. I should clarify: the bit about substituting the complement of $\sigma(1)$ was motivated by an application I have in mind. $\endgroup$ – Shane Steinert-Threlkeld Jun 9 '13 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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