The State Complexity of Lexicographically Smallest Words and Computing Successors.

Given a regular language L over an ordered alphabet \(\varSigma \), the set of lexicographically smallest (resp., largest) words of each length is itself regular. Moreover, there exists an unambiguous finite-state transducer that, on a given word \(w \in \varSigma ^*\), outputs the length-lexicographically smallest word larger than w (henceforth called the L-successor of w). In both cases, naive constructions result in an exponential blowup in the number of states. We prove that if L is recognized by a DFA with n states, then \(2^{\varTheta (\sqrt{n \log n})}\) states are sufficient for a DFA to recognize the subset S(L) of L composed of its lexicographically smallest words. We give a matching lower bound that holds even if S(L) is represented as an NFA. We then show that the same upper and lower bounds hold for an unambiguous finite-state transducer that computes L-successors.