论文标题
词典最小的单词和计算后继的状态复杂性
The State Complexity of Lexicographically Smallest Words and Computing Successors
论文作者
论文摘要
鉴于有序字母$σ$的常规语言L，每个长度的词典最小（分别，最大）单词本身是常规的。此外，存在一个明确的有限态传感器，在给定的单词W上，输出长度图上最小的单词最小的单词（此后称为W的L-Successor）。在这两种情况下，幼稚的结构都会导致状态数量的指数爆炸。我们证明，如果l被n个状态的DFA识别，则$ 2^{θ（\ sqrt {n \ log n}）}} $状态足以让DFA识别由其词典上最小单词组成的子集S（l）的子集S（l）。我们给出了一个匹配的下限，即使S（L）表示为NFA，也可以保留。然后，我们证明，相同的上限和下边界适用于计算L服务器的明确有限状态传感器。
Given a regular language L over an ordered alphabet $Σ$, 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^{Θ(\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.
