Complexidade do problema das palavras com o menor número de letras distintas aceitas por um autômato finito

Dado um autômato finito (determinístico ou não determinístico, acho que isso não tem muita importância) autômato A e um limiar n , A aceita uma palavra contendo no máximo n letras distintas?

(Com k letras diferentes, quero dizer que aabaa tem duas letras distintas, a e b .)

Eu mostrei esse problema como NP-completo, mas minha redução produz autômatos nos quais a mesma letra aparece em muitas transições.

Estou bastante interessado nos casos em que cada letra aparece no máximo k vezes em A, onde k é um parâmetro fixo. O problema ainda está completo?

Para k = 1, o problema é apenas o caminho mais curto, assim como P. Para k = 2, eu não consegui mostrar associação em P nem encontrar uma prova de dureza NP.

Alguma idéia, pelo menos para k = 2?

$k=3$$3$$2$

$k$$st$$n$

$s$$n$$n$$2n$$n$