  Given a regular language L over an ordered alphabet $\Sigma$, 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, 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^{\Theta(\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.
