Unambiguity and Fewness for Nonuniform Families of Polynomial-Size
  Nondeterministic Finite Automata
Tomoyuki Yamakami
Nonuniform families of polynomial-size finite automata, which are series of
indexed finite automata having polynomially many inner states, are used in the
past literature to solve nonuniform families of promise decision problems.
Among such nonuniform families of finite automata, we focus our attention, in
particular, on the variants of nondeterministic finite automata, which have at
most "one" (unambiguous), "polynomially many" (few) accepting computation
paths, or unambiguous/few computation paths leading to each fixed
configuration. When such machines are limited to make only one-way head moves,
we can prove with no unproven hardness assumptions that some of these variants
are different in computational power from each other. As for two-way machines
restricted to instances of polynomially-bounded length, families of two-way
polynomial-size nondeterministic finite automata are equivalent in power to
families of polynomial-size unambiguous finite automata.