Nondeterministic Tree Width of Regular Languages

摘要

The tree width of a nondeterministic finite automaton (NFA) counts the maximum number of computations the automaton may have on a given input. Here we consider the tree width of a regular language, which, roughly speaking, measures the amount of nondeterminism that a state-minimal NFA for the language needs. We prove that an infinite tree width is obtained from finite tree width, for most operations on regular languages.