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.

  • $\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

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


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.