Show simple item record

dc.contributor.authorPalioudakis, Alexandros
dc.contributor.otherQueen's University (Kingston, Ont.). Theses (Queen's University (Kingston, Ont.))en
dc.date2014-09-13 22:44:13.42en
dc.date.accessioned2014-09-15T15:48:28Z
dc.date.available2014-09-15T15:48:28Z
dc.date.issued2014-09-15
dc.identifier.urihttp://hdl.handle.net/1974/12453
dc.descriptionThesis (Ph.D, Computing) -- Queen's University, 2014-09-13 22:44:13.42en
dc.description.abstractVarious approaches of quantifying nondeterminism in nondeterministic finite automata (NFA) are considered. We consider nondeterministic finite automata having finite tree width (ftw-NFA) where the computation on any input string has a constant number of branches. We give effective characterizations of ftw-NFAs and a tight bound for determinizing an ftw-NFA A as a function of the tree width and the number of states of A. We introduce a lower bound technique for ftw-NFAs. We study the interrelationships between various measures of nondeterminism for finite automata. We define the trace measure which is a new approach of quantifying nondeterminism. The trace is defined in terms of the maximum product of the degrees of nondeterministic choices in any computation. We establish upper and lower bounds for the trace of an NFA in terms of its tree width. It is known that an NFA with n states and branching k can be simulated by a deterministic finite automaton with multiple initial states (MDFA) having kn states. We give a lower bound (k/(1+\logk))n for the size blow-up of this conversion. We also consider bounds for the number of states an MDFA needs to simulate a given NFA of finite tree width. We consider unary NFA employing limited nondeterminism. We show that for unary regular languages, minimal ftw-NFAs can always be found in Chrobak normal form. A similar property holds with respect to other measures of nondeterminism. The latter observation is used to establish, for a given unary regular language, relationships between the sizes of minimal NFAs where the nondeterminism is limited in various ways. We study also the state complexity of language operations for unary NFAs with limited nondeterminism. We consider the operations of concatenation, Kleene star, and complement. We give upper bounds for the state complexity of these language operations and lower bounds that are fairly close to the upper bounds. Finally, we show that the branching measure (J. Goldstine, C. Kintala, D. Wotschke, Inf. and Comput vol 86, 1990, 179-194) of a unary NFA is always either bounded by a constant or has an exponential growth rate.en_US
dc.languageenen
dc.language.isoenen_US
dc.relation.ispartofseriesCanadian thesesen
dc.rightsThis publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.en
dc.subjectunary regular languagesen_US
dc.subjectfinite automataen_US
dc.subjectlimited nondeterminismen_US
dc.subjectdeterministic automata with multiple initial statesen_US
dc.subjectlanguage operationsen_US
dc.subjectstate complexityen_US
dc.titleState Complexity of Nondeterministic Finite Automata with Limited Nondeterminismen_US
dc.typethesisen_US
dc.description.degreePh.Den
dc.contributor.supervisorAkl, Selimen
dc.contributor.supervisorSalomaa, Kai Jren
dc.contributor.departmentComputingen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record