Given a finite (deterministic or nondeterministic, I don't think this has much importance) automaton A and a threshold n, does A accept a word containing at most n distinct letters?
(By k different letters I mean that aabaa has two distinct letters, a and b.)
I showed this problem to be NP-complete, but my reduction produces automata in which the same letter appears on many transitions.
I'm rather interested in the cases where each letter appears at most k times in A, where k is a fixed parameter. Is the problem still NP-complete?
For k=1 the problem is just shortest path, so is P. For k=2 I've neither been able to show membership in P nor to find a proof of NP-hardness.
Any idea, at least for k=2 ?