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 constant delay bounds, 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 constant. 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$ recognizing a language $L$, we can compute in PTIME automata $A_1, \ldots, A_t$ such that $L$ 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 this is optimal, i.e., we cannot partition $L$ into less than $t$ orderable languages. In the case where $L$ is orderable, we show that the ordering can be computed as a constant-delay algorithm: specifically, the algorithm runs in a suitable pointer machine model, and produces a sequence of constant-length edit scripts to visit the words of $L$ without repetitions, with constant delay 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. We also show results on the complexity of a related problem, and study the model where push-pop edits are only allowed at the end of the word.
翻译:对于给定语言,我们研究一个任务,即对于给定语言来说,一个任务(L$$ ), 计算其单词的(一般无限的)序列, 而不重复, 同时在连续两个单词之间限制延迟。 为了允许持续延迟的界限, 我们假设一个模式, 我们通过编辑前一个单词, 编辑一个小的编辑脚本, 而不是从头写出单词。 特别是, 这个证人, 语言是可排序的, 也就是说, 我们可以用无限的顺序来编辑任何连续两个单词之间的距离。 例如, $(a+b) $ (美元) 无法在连续的两个单词之间设置一个常数 。 例如, $(a+) $(美元) 是无法连续的。 但是, $(a) +% (b) 不是固定的单数, 并显示一个正常的文字在输入确定性自动的自动调。 事实上, 我们只能用一个最高级的单数(dA$) 来显示一个最高级的单词, 在模型中, 我们也可以用一个最高级的演示一个不显示 $A_ 1 。