Growth Rate of Minimum Branching

Abstract

There are different ways of quantifying the nondeterminism used by a nondeterministic finite automaton (NFA). The amount of nondeterminism is measured as a function of the input length. For most nondeterminism measures the possible growth rates of the measure have been characterized, but this question remains open for the branching of an NFA. Here, we consider a close variant of the branching measure which we call the minimum branching. We show that the minimum branching of an NFA is always either bounded or grows exponentially.