Problem Detail: A class of languages $mathcal{C}$ is closed under countable union (cucu) if for all series of languages in $mathcal{C}$ ($(L_i)_{iinmathbb{N}} in mathcal{C}^mathbb{N}$) the language $bigcup_{iinmathbb{N}}L_i = {xmid exists iinmathbb{N}: x in L_i}$ is an element of $mathcal{C}$. As we know most (if not all but $mathsf{ALL} = wp(Sigma^*)$) interesting complexity classes are not closed under countable union as every Language $L$ is the countable union of some singleton Laguages ${w_i}$. However there are some classes of decidable languages which are cucu like:
- ${{winSigma^*mid |w| leq i}mid iinmathbb{N}}$
- ${ntext{-}mathrm{SAT}mid ninmathbb{N}}$
- every $mathcal{C}$ s.t. every $L in mathcal{C}$ is cofinite
My questions:
- Let $mathcal{C},mathcal{C’} subset mathsf{REC}$ be two classes of decidable languages s.t. both are cucu. Is $mathcal{C} cup mathcal{C’}$ cucu?
- Is there some “real” complexity class (i.e. defined by some machine model, grammar type, $lambda$-calculus restriction etc.) that is cucu? (You may restrict it artificially (e.g. NFA, where each final state has a path to another final state), if it fits otherwise.)
- Edit (after Yuval Filmus’ answer): Given $mathcal{C},mathcal{C’}$, as in (1), does the closure of $mathcal{C} cup mathcal{C’}$ under countable union only contain decidable languages?
(1) is the main question, (2+3) only addenda.
Asked By : frafl
Answered By : Yuval Filmus
The answer to (3) is yes. Suppose that $S subseteq mathcal{C} cup mathcal{C}’$. Then $S$ is countable, because $mathcal{C}cupmathcal{C’}$ contains only decidable languages of which there are only countable many. Now let $T = S cap mathcal{C}$, $T’ = S cap mathcal{C}’$. By assumption $L = bigcup T in mathcal{C}$, $L’ = bigcup T’ in mathcal{C}’$. Since $L,L’$ are decidable, $L cup L’$ is decidable.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10648 Ask a Question Download Related Notes/Documents
