Usefulness of information and decomposability of unary regular languages

We continue the research on usefulness of information examining the effect of supplementary information on the complexity of solving a problem. We use DFAs for a formal setting. Given a problem (a regular language) Lprob we measure the complexity of its solution — a DFA Aprob accepting Lprob — using the state complexity. A supplementary information (advice) Ladv given by Aadv is useful if a simpler problem Lnew given by Anew exists such that Lprob=Lnew∩Ladv and both Lnew and Ladv are simpler than Lprob. This is formalized via the notion of decomposability of finite automata and regular languages. We address the problem of deterministic decomposability of unary regular languages. We give a characterization upon deterministic decomposability for the class of unary regular languages and we discuss the problem of deciding whether a given DFA over unary alphabet is decomposable (UDFA-DECOMPOSABILITY problem).