# Partitions of star-free languages and questions on the proof of the Splitting Lemma by Diekert/Gastin

I'm currently reading a paper on First-order definable languages by Volker Diekert and Paul Gastin. Im having trouble understanding a part of the proof for lemma 3.2 (splitting lemma). The part I'm having a problem with, is about the complement:

(Note: I've substituted $$B^\infty = B^* \cup B^\omega$$ with $$B^*$$ which shouldn't cause problems)

From the paper:

It remains to deal with the complement $$\Sigma^* \setminus L$$ of a star-free set. By induction, we have $$L \cap B^* A B^* = \bigcup_{1 \leq i \leq n} K_iAL_i$$. If some $$K_i$$ and $$K_j$$ are not disjoint then we can rewrite $$K_iAL_i \cup K_jAL_j = (K_i \setminus K_j)AL_i \cup (K_j \setminus K_i)AL_j \cup (K_i \cap K_j)A(L_i\cup L_j)$$ We can also add $$(B^* \setminus \bigcup_{i} K_i)A \emptyset$$ in case $$\bigcup_{i}K_i$$ is strictly contained in $$B^*$$. Therefore, we may assume that $$\{K_i \mid 1 \leq i \leq n\}$$ forms a partition of $$B^*$$. This yields: $$(\Sigma^* \setminus L) \cap B^*AB^* = \bigcup_{1\leq 1 \leq n} K_iA(B^* \setminus L_i)$$

Questions:

1. In the last part of the proof $$\bigcup_{1\leq 1 \leq n} K_iA(B^* \setminus L_i)$$, why is it enough to only build the complement for $$L_i$$ with $$B^* \setminus L_i$$? Why don't we need $$B^* \setminus K_i$$?
2. Why does $$\{K_i \mid 1 \leq i \leq n\}$$ form a partition of $$B^*$$?

1. For the set $$\{K_i \mid 1 \leq i \leq n\}$$ to form a partition of $$B^*$$, it is necessary, that all $$K_i$$ are pairwise disjoint and every element in $$B^*$$ is cointained in some $$K_i$$. You already showed that they are disjoint, as is is possible to split two overlapping $$K_i$$ into three disjoint ones by using the parts that don't overlap and the intersection instead. The second condition, that everything is contained, is achieved by adding $$(B^* \setminus \bigcup_i K_i)$$ to the set $$\{K_i \mid 1 \leq i \leq n\}$$ so $$n$$ is incresed by one and still is finite. And this $$(B^* \setminus \bigcup_i K_i)$$ contains everything that was not previously contained.
2. As $$\{K_i \mid 1 \leq i \leq n\}$$ forms a partition, everything in $$B^*$$ is contained in some $$K_i$$ and is, therefore, also contained in the complement of another one, which means, it doesn't change anything to use the complement of the $$K_i$$s.