Breaking the $4^k$ Barrier for the $k$-Distinct Language

Ran Ben Basat

For integers $k\le n$, let $L_{k,n}$ be the set of words over $[n]$ of length at most $k$ in which no symbol is repeated. We present a nondeterministic finite automaton (NFA) of si…