Description
We continue the research of the notion of usefulness of information.
We formalize a problem by a regular language $L$ and we measure its complexity using the state complexity of the minimal automaton $A$ accepting the language $L$.
A language $L_{adv}$ provides a useful supplementary information about the problem, if it allows us to solve the problem easier, i.e., if it allows us to find an easier problem $L_{new}$ such that $L = L_{adv} \cap L_{new}$.
Moreover, we require to check the correctness of supplementary information to be easier than to solve the original problem.
We formalize this concept using the decomposition of the automaton $A$ formed by automata $A_{adv}$ and $A_{new}$ accepting the languages $L_{adv}$ and $L_{new}$, respectively.
We study the family of all problems for which a given unary language $L_A$ provides useful information.
We also consider decompositions of regular languages bounded by $a^∗b^∗$ (languages that are a subset of $a^∗b^∗$) and we characterize a subclass of these languages upon decomposition.
| Pracovisko fakulty (katedra)/ Department of Faculty | Katedra informatiky |
|---|---|
| Tlač postru/ Print poster | Budem požadovať tlač /I hereby required to print the poster in faculty |
