| Meno: | Matúą
|
|---|
| Priezvisko: | Juran
|
|---|
| Názov: | Supplementary Information and Transducers
|
|---|
| Vedúci: | prof. RNDr. Branislav Rovan, PhD.
|
|---|
| Rok: | 2019
|
|---|
| Kµúčové slová: | supplementary information, transducers, state complexity, regular languages
|
|---|
| Abstrakt: | This thesis is a part of the research on various aspects of the notion of information.
Supplementary information (advice) may reduce the complexity of solving a problem
in some cases. The notion of usefulness of supplementary information was studied in
the finite automata setting and in the deterministic push-down automata setting. In
this thesis, we study the possibility of exploiting supplementary information in finite
transducers setting. The notion of advice is formalized as a regular language which
the transducer transforms to a different regular language. We consider the advice to
be useful if the transducer requires fewer states than it would require to transform the
language of all strings over the input alphabet. This approach can be used with either
deterministic or nondeterministic transducer as a computational model. We define
families of languages for which useful advice exists and show particular languages
that belong to these families. We compare these families to the families defined by
decomposability of automata studied earlier and study their closure properties. We
show that some modifications of the advice can affect its usefulness. We also study the
families defined by a fixed advice language.
|
|---|