State Complexity of Nondeterministic Finite Automata with Limited Nondeterminism

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.