Closure of Star-Free Languages under Substitution

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?)

• Star-free expressions use Boolean operators. Isn't the problem that $\sigma(K\cap L) \neq \sigma(K) \cap \sigma(L)$? 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.

• 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. Jun 9 '13 at 0:37

Substitutions are a rather broad class of mappings. Let me show that star-free languages are not even closed under projection mappings. A projection mapping is a special homomorphism given by deleting letters. More formally, if $$\Gamma \subseteq \Sigma$$, then the projection onto $$\Gamma^*$$ is given by $$\pi_{\Gamma}(x) = x$$ for $$x \in \Gamma$$ and $$\pi_{\Gamma}(x) = \varepsilon$$ otherwise, and extended to all of $$\Sigma^*$$. Now, the language $$L = (aba)^*$$ is star-free, as $$L = \{\varepsilon\} \cup (aba\Sigma^* \cap \Sigma^*aba) \setminus (\Sigma^*\cdot\{aaa,bba,bab,abb\}\cdot\Sigma^*).$$ However, $$\pi_{\{a\}}(L) = (aa)^*$$ is not star-free.

Finally, let me mention that the commutative star-free languages are closed under projections. Note that the star-free languages coincide with the aperiodic languages.

I present a proof, using the following characterization from J.E.Pin, Syntactic Semigroups (Handbook of Formal Languages):

For a given alphabet $$\Sigma$$, the class of aperiodic and commutative languages over $$\Sigma$$ is the boolean algebra generated by the languages $$F(a, k)$$ with $$a \in \Sigma$$ and $$k \ge 0$$, where $$F(a, k) = \{ u \in \Sigma^+ : |u|_a \ge k \}$$ and $$|u|_a$$ denotes the number of $$a$$'s in $$u \in \Sigma^*$$.

Set, for $$k_1, k_2 \in \mathbb N_0 \cup \{\infty\}$$ and $$a \in \Sigma$$, with the obvious extensions of the operations to $$\mathbb N_0 \cup \{\infty\}$$, $$F(a, k_1, k_2) = \{ u \in \Sigma^* : k_1 \le |u|_a < k_2 \}.$$ By using the laws of a boolean algebra, we can write an aperiodic and commutative language as a finite union of intersections of sets $$F(a, k)$$ and complements $$\overline{F(a,k)}$$. Such an intersection could be rewritten as an intersection of sets $$F(a, k_1, k_2)$$ as above, each such set corresponding to a different letter. As function application on sets preserves union, we only need to consider such intersections. We can suppose each set $$F(a, k_1, k_2)$$ is non-empty. Then, the projection equals the intersection over those languages $$F(a, k_1, k_2)$$ with $$a \in \Gamma$$, the other are left out. So, in total, the projection is a boolean combination of sets of the form $$F(a, k_1, k_2)$$ with $$a \in \Gamma$$. Hence, an aperiodic and commutative language over $$\Gamma$$.