Abstract
dc:descriptionTransducers are finite state automata with an output. In this thesis, we attempt to classify sequences that can be constructed by iteratively applying a transducer to a given word. We begin exploring this problem by considering sequences of words that can be produced by iterative application of a transducer to a given input word, i.e., identifying sequences of words of the form w, t(w), t²(w), . . . We call such sequences transducer recognizable. Also we introduce the notion of "recognition of a sequence in context", which captures the possibility of concatenating prefix and suffix words to each word in the sequence, so a given sequence of words becomes transducer recognizable. It turns out that all finite and periodic sequences of words of equal length are transducer recognizable. We also show how to construct a deterministic transducer with the least number of states recognizing a given sequence. To each transducer t we associate a two-dimensional language L²(t) consisting of blocks of symbols in the following way. The first row, w, of each block is in the input language of t, the second row is a word that t outputs on input w. Inductively, every subsequent row is a word outputted by the transducer when its preceding row is read as an input. We show a relationship of the entropy values of these two-dimensional languages to the entropy values of the one-dimensional languages that appear as input languages for finite state transducers.
Degree
thesis:*- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Mathematics and Statistics
- Grantor
- University of South Florida
- Year dc:date
- 2007
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Dolzhenko, Egor
- Contributors dc:contributor
-
- Natasha Jonoska, Ph.D.
- Brian Curtin, Ph.D.
- Gregory McColm, Ph.D.
Subjects
dc:subject × 7Rights
- Language dc:language
- EN-US
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.usf.edu/etd/217