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


  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 Answer 1

  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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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