2020/03/18 by Lukas Fleischer, Jeffrey Shallit, Fleischer, Lukas +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2003.08249
openalex publication_date 2020/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a regular language L over an ordered alphabet \Σ, the set of\nlexicographically smallest (resp., largest) words of each length is itself\nregular. Moreover, there exists an unambiguous finite-state transducer that, on\na given word w, outputs the length-lexicographically smallest word larger than\nw (henceforth called the L-successor of w). In both cases, naive constructions\nresult in an exponential blowup in the number of states. We prove that if L is\nrecognized by a DFA with n states, then 2\Θ(\√(n \log n)) states\nare sufficient for a DFA to recognize the subset S(L) of L composed of its\nlexicographically smallest words. We give a matching lower bound that holds\neven if S(L) is represented as an NFA. We then show that the same upper and\nlower bounds hold for an unambiguous finite-state transducer that computes\nL-successors.\n