Advertisement
Published in:
2021 | OriginalPaper | Chapter
Usefulness of Information and Unary Languages
Authors : Giovanni Pighizzini, Branislav Rovan, Šimon Sádovský
Published in: Language and Automata Theory and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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) \(L_{prob}\) we measure the complexity of its solution – a DFA \(A_{prob}\) such that \(L_{prob} = L(A_{prob})\) – using the state complexity. A supplementary information (advice) \(L_{adv}\) given by \(A_{adv}\) is useful if a simpler problem \(L_{new}\) given by \(A_{new}\) exists such that \(L_{prob} = L_{new} \cap L_{adv}\) and both \(L_{new}\) and \(L_{adv}\) are simpler than \(L_{prob}\). 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 \(\lambda \)-cyclic languages upon deterministic decomposability.