Meno:Ivan
Priezvisko:Kováč
Názov:Equiloaded Automata
Vedúci:prof. RNDr. Branislav Rovan, PhD.
Rok:2010
Blok:INF
Kµúčové slová:equiloaded automata, balanced use of resources, deterministic finite automata
Abstrakt:In this thesis we initiate the study of a balanced use of resources in computations. We consider a particular model of computation --- deterministic finite automata --- and take states as the resource to be used in a balanced way. In this setting we develop notions and prove results which can serve as an example for similar studies in other settings. Three possible approaches to define a balanced use of states by deterministic finite automaton are investigated: a strict equiloadedness, an equiloadedness, and an equiloadedness on sequences of words. We analyze properties of families of automata and languages with respect to different definitions of balanced use of states. We show a characterization of the family of languages for which there exists a strictly equiloaded automaton. We exhibit the closure properties of this family based on this characterization. The family of languages for which there exists an equiloaded automaton is analyzed by proving closure properties, by providing a necessary condition for a language to be in this family, and by defining a set of transformations that preserve the equiloadedness of an automaton. Considering equiloadedness on sequences of words, we analyze the influence of different orderings of words on the equiloadedness tolerance. We investigate the equiloadedness on sequences for various bounds on the equiloadedness tolerance function.

Súbory diplomovej práce:

thesis.pdf