Usefulness of Information and Unary Languages

In this paper we continue the research on usefulness of information examining the effect of supplementary information on the complexity of solving a problem (see Rovan and Sádovský [7] for an overview). We use deterministic finite automata for a formal setting. Given a problem (a regular language) LprobLprob we measure the complexity of its solution – a DFA AprobAprob such that Lprob=L(Aprob)Lprob=L(Aprob) – using the state complexity. A supplementary information (advice) LadvLadv given by AadvAadv is useful if a simpler problem LnewLnew given by AnewAnew exists such that Lprob=Lnew∩LadvLprob=Lnew∩Ladv and both LnewLnew and LadvLadv are simpler than LprobLprob. This is formalized via the notion of decomposability of finite automata (see [1] for DFA case and [7] for NFA case). We address the problem of decomposability of unary regular languages and give a characterization of λλ-cyclic languages upon deterministic decomposability