• Login
    View Item 
    •   Home
    • Graduate Theses, Dissertations and Projects
    • Queen's Graduate Theses and Dissertations
    • View Item
    •   Home
    • Graduate Theses, Dissertations and Projects
    • Queen's Graduate Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    State Complexity of Nondeterministic Finite Automata with Limited Nondeterminism

    Thumbnail
    View/Open
    Palioudakis_Alexandros_201409.pdf (1.027Mb)
    Date
    2014-09-15
    Author
    Palioudakis, Alexandros
    Metadata
    Show full item record
    Abstract
    Various 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.
    URI for this record
    http://hdl.handle.net/1974/12453
    Collections
    • Queen's Graduate Theses and Dissertations
    • School of Computing Graduate Theses
    Request an alternative format
    If you require this document in an alternate, accessible format, please contact the Queen's Adaptive Technology Centre

    DSpace software copyright © 2002-2015  DuraSpace
    Contact Us
    Theme by 
    Atmire NV
     

     

    Browse

    All of QSpaceCommunities & CollectionsPublished DatesAuthorsTitlesSubjectsTypesThis CollectionPublished DatesAuthorsTitlesSubjectsTypes

    My Account

    LoginRegister

    Statistics

    View Usage StatisticsView Google Analytics Statistics

    DSpace software copyright © 2002-2015  DuraSpace
    Contact Us
    Theme by 
    Atmire NV