| 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.
|
|---|