State-complexity hierarchies of uniform languages of alphabet-size length

Abstract

We study the state complexity of a special class of simple languages. If A is an alphabet of k letters, then a k-language is a nonempty set of words of length k, that is, a uniform language of length k. We show that every k-language of maximal state complexity is also a uniform language of length k of maximal state complexity. Moreover, we prove that, for every i between the minimal and the maximal state complexities, there is a language of complexity i. The proof is constructive: for each i we exhibit a language of complexity i. We introduce a family of "pi automata" accepting languages whose words are permutations of the alphabet; the complexities of these languages form a complete hierarchy between k^2-k+3 and 2^k+1. We start with an automaton with k^2-k+3 states and show that states can be added one at a time, until the automaton has 2^k+1 states. We construct another family of automata, based on k-ary trees, whose languages define a complete hierarchy of complexities between 2^k+1 and the maximal complexity. Here, we start with an automaton with the maximal complexity. Here, we start with an automaton with the maximal number of states and remove states one at a time, until an automaton with 2^k+1 and the maximal complexity. Here, we start with an automaton with the maximal number of states and remove states one at a time, until an automaton with 2^k+1 states is reached.