论文标题
用有限的延迟列举普通语言
Enumerating Regular Languages with Bounded Delay
论文作者
论文摘要
我们研究给定语言$ l $的任务，列举了单词的（通常是无限的）序列，而无需重复，同时限制了两个连续两个单词之间的延迟。为了允许不依赖当前单词长度的延迟界限，我们假设一个模型通过使用小编辑脚本编辑前一个单词来产生每个单词，而不是从头开始写出单词。特别是，这见证了语言是有序的，即我们可以将其单词写成无限的序列，以使Levenshtein编辑任何两个连续单词之间的编辑距离受一个仅取决于语言的值的界限。例如，$（a + b）^*$是订购的（带有灰色代码的变体），但是$ a^* + b^*$不是。 我们表征了哪种普通语言在这个意义上是可以枚举的，并表明可以在Ptime中以该语言的输入确定性有限自动机（DFA）确定。实际上，我们表明，在dfa $ a $中，我们可以在ptime automata $ a_1，\ ldots，a_t $中计算$ l（a）$的$ l（a_1）\ sqcup \ ldots \ ldots \ ldots \ ldots \ sqcup l（a_t）$（a_t）$（a_t）$（a_i）$（a_i）$。此外，我们表明，获得的$ t $的值是最佳的，即，我们不能将$ l（a）$划分为小于$ t $订购的语言。 In the case where $L(A)$ is orderable (i.e., $t=1$), we show that the ordering can be produced by a bounded-delay algorithm: specifically, the algorithm runs in a suitable pointer machine model, and produces a sequence of bounded-length edit scripts to visit the words of $L(A)$ without repetitions, with bounded delay -- exponential in $|A|$ -- between each script.实际上，我们表明我们可以实现这一目标，同时只允许编辑操作在单词的开头和结尾处推动和弹出，这意味着该单词实际上可以在双层队列中维持。
We study the task, for a given language $L$, of enumerating the (generally infinite) sequence of its words, without repetitions, while bounding the delay between two consecutive words. To allow for delay bounds that do not depend on the current word length, we assume a model where we produce each word by editing the preceding word with a small edit script, rather than writing out the word from scratch. In particular, this witnesses that the language is orderable, i.e., we can write its words as an infinite sequence such that the Levenshtein edit distance between any two consecutive words is bounded by a value that depends only on the language. For instance, $(a+b)^*$ is orderable (with a variant of the Gray code), but $a^* + b^*$ is not. We characterize which regular languages are enumerable in this sense, and show that this can be decided in PTIME in an input deterministic finite automaton (DFA) for the language. In fact, we show that, given a DFA $A$, we can compute in PTIME automata $A_1, \ldots, A_t$ such that $L(A)$ is partitioned as $L(A_1) \sqcup \ldots \sqcup L(A_t)$ and every $L(A_i)$ is orderable in this sense. Further, we show that the value of $t$ obtained is optimal, i.e., we cannot partition $L(A)$ into less than $t$ orderable languages. In the case where $L(A)$ is orderable (i.e., $t=1$), we show that the ordering can be produced by a bounded-delay algorithm: specifically, the algorithm runs in a suitable pointer machine model, and produces a sequence of bounded-length edit scripts to visit the words of $L(A)$ without repetitions, with bounded delay -- exponential in $|A|$ -- between each script. In fact, we show that we can achieve this while only allowing the edit operations push and pop at the beginning and end of the word, which implies that the word can in fact be maintained in a double-ended queue.
