On the union of 0L languages (Q685483)

The authors treat the problem of union of two 0L languages. They show that in general this question is undecidable and that it becomes decidable in the case of PD0L languages and languages over unary alphabets. The following are the main results: Theorem 1. For arbitrarily given (P)0L languages L1 and L2, it is undecidable whether L1 \(\cup\) L2 is a 0L language (or a P0L language). Theorem 2. It is decidable whether or not the union of two PD0L languages is a PD0L language. Theorem 3. Given two 0L languages over a unary alphabet it is decidable whether or not their union is 0L language.