Názov:Supplementary Information and Transducers
Vedúci:prof. RNDr. Branislav Rovan, PhD.
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.

Súbory bakalárskej práce: