Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

Question

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 ?

Answer 1

It is NP-hard for $k=3$. The reduction is from 3-SAT-(2,2), which means that every clause contains $3$ literals and every literal occurs in at most $2$ clauses.

First of all, for simplicity, let's admit honestly that this problem has not much to do with automata. Your problem is equivalent to the following: Given an edge-colored digraph where each color occurs at most $k$ times, is there an $st$ path that uses at most $n$ colors?

For the reduction, the graph starts from $s$ with a path of length $n$, where $n$ is the number of variables of the 3-SAT-(2,2) input. Each edge of this path is present twice, and all $2n$ edges have a different color. The colors used when traversing this path correspond to which variables are true. After this path, there is another path whose length is the number of clauses. Here every edge is thrice, where the colors correspond to the literals of the clause. We can get to the end of this path using no extra colors (thus in total $n$) if and only if the 3-SAT-(2,2) input is satisfiable.