Enumerating Regular Languages with Bounded Delay

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 boundsthat do not depend on the current word length, we assume a model where we produce each word by editingthe 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 theLevenshtein edit distance between any two consecutive words is bounded by a value that depends only on thelanguage. 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 inPTIME in an input deterministic finite automaton (DFA) for the language. In fact, we show that, given aDFA A, we can compute in PTIME automata A1, .. ., At such that L(A) is partitioned as L(A1 ) ⊔. .. ⊔ L(At )and every L(Ai ) is orderable in this sense. Further, we show that the value of t obtained is optimal, i. e. , wecannot 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-delayalgorithm: specifically, the algorithm runs in a suitable pointer machine model, and produces a sequence ofbounded-length edit scripts to visit the words of L(A) without repetitions, with bounded delay – exponentialin |A| – between each script. In fact, we show that we can achieve this while only allowing the edit operationspush and pop at the beginning and end of the word, which implies that the word can in fact be maintained ina double-ended queue. By contrast, when fixing the distance bound d between consecutive words and the number of classes of thepartition, it is NP-hard in the input DFA A to decide if L(A) is orderable in this sense, already for finitelanguages. Last, we study the model where push-pop edits are only allowed at the end of the word, corresponding to acase where the word is maintained on a stack. We show that these operations are strictly weaker and that theslender languages are precisely those that can be partitioned into finitely many languages that are orderablein this sense. For the slender languages, we can again characterize the minimal number of languages in thepartition, and achieve bounded-delay enumeration. This is joint work with Mikaël Monet, and was presented at STACS’23. Contributed talk given by Antoine Amarilli

Authors

• Antoine Amarilli

Keywords

No keywords are indexed for this paper.