Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata

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. In such a nonuniform family, we focus our attention, in particular, on the variants of nondeterministic finite automata, which have at most "one" (unique or unambiguous), "polynomially many" (few) accepting computation paths, or unique/few computation paths leading to each fixed configuration. We prove that those variants of one-way machines are different in computational power. As for two-way machines restricted to instances of polynomially-bounded size, families of two-way polynomial-size nondeterministic finite automata are equivalent in power to families of unambiguous finite automata.