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?)
Closure of Star-Free Languages under Substitution
formal languages;regular languages;closure properties
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 inthe literature on star-free RE. But all closure results under substitution putconstraints on the type of substitution, such as being lengthpreserving, 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 checkthe 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. Thrien. Some results on the generalized star-height problem. May 12 2002.