| Meno: | Vincent |
|---|---|
| Priezvisko: | Hlaváč |
| Názov: | Power of supplementary information for unary regular languages |
| Vedúci: | prof. RNDr, Branislav Rovan, PhD. |
| Rok: | 2025 |
| Kµúčové slová: | usefulness of information, advice, unary deterministic finite automaton, decomposability, decomposition, quality of decomposition, power of supplementary information, state complexity |
| Abstrakt: | In this thesis we continue the research of the notion of usefulness of information. We formalize a problem by a unary 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 define a relation on languages \textit{provide useful information} and the family of all problems for which a given language $L_A$ provides useful information. We prove that this family is infinite for every infinite language $L_A \neq a^*$. We investigate relations between inclusion of these families, inclusion of the respective languages and the relation \textit{provide useful information}. Next, we prove a counterintuitive fact that the relation \textit{provide useful information} is not transitive. Furthermore, we measure the quality of decompositions using the maximum and the product of the state complexities of automata forming a decomposition. |
Súbory diplomovej práce:
| masters_thesis_hlavac.pdf |
Súbory prezentácie na obhajobe: