Enumerating Regular Languages with Bounded Delay
Type de document :
Communication dans un congrès avec actes
Titre :
Enumerating Regular Languages with Bounded Delay
Auteur(s) :
Amarilli, Antoine [Auteur]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Institut Polytechnique de Paris [IP Paris]
Monet, Mikaël [Auteur]
Linking Dynamic Data [LINKS]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Institut Polytechnique de Paris [IP Paris]
Monet, Mikaël [Auteur]
Linking Dynamic Data [LINKS]
Titre de la manifestation scientifique :
STACS
Ville :
Hamburg
Pays :
Allemagne
Date de début de la manifestation scientifique :
2023-03-07
Date de publication :
2023
Mot(s)-clé(s) en anglais :
Regular language
Constant-delay enumeration
Edit distance
constant-delay enumeration
edit distance
Theory of computation → Formal languages and automata theory
Constant-delay enumeration
Edit distance
constant-delay enumeration
edit distance
Theory of computation → Formal languages and automata theory
Discipline(s) HAL :
Informatique [cs]
Résumé en anglais : [en]
We study the task, for a given language $L$, of enumerating the (generallyinfinite) sequence of its words, without repetitions, while bounding thedelay between two consecutive words. To allow for delay bounds that do not ...
Lire la suite >We study the task, for a given language $L$, of enumerating the (generallyinfinite) sequence of its words, without repetitions, while bounding thedelay 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 witha small edit script, rather than writing out the word from scratch. Inparticular, this witnesses that the language is orderable, i.e., we canwrite its words as an infinite sequence such that the Levenshtein edit distancebetween 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^*$ isnot.We characterize which regular languages are enumerable in this sense, andshow that this can be decided in PTIME in an input deterministic finiteautomaton (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 partitionedas $L(A_1) \sqcup \ldots \sqcup L(A_t)$ and every $L(A_i)$ is orderable inthis 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 beproduced by a bounded-delay algorithm: specifically, the algorithm runs in asuitable pointer machine model, and produces a sequence of bounded-length editscripts 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 onlyallowing the edit operations push and pop at the beginning andend 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 wordsand the number of classes of the partition, it is NP-hard in the input DFA $A$to decide if $L(A)$ is orderable in this sense, already for finite languages. Last, we study the model where push-pop edits are only allowed at the end ofthe word, corresponding to a case where the word is maintained on a stack.We show that these operations are strictly weaker and that the slenderlanguages are precisely those that can be partitioned into finitely manylanguages that are orderable in this sense. For the slender languages, we can againcharacterize the minimal number of languages in the partition, and achievebounded-delay enumeration.Lire moins >
Lire la suite >We study the task, for a given language $L$, of enumerating the (generallyinfinite) sequence of its words, without repetitions, while bounding thedelay 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 witha small edit script, rather than writing out the word from scratch. Inparticular, this witnesses that the language is orderable, i.e., we canwrite its words as an infinite sequence such that the Levenshtein edit distancebetween 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^*$ isnot.We characterize which regular languages are enumerable in this sense, andshow that this can be decided in PTIME in an input deterministic finiteautomaton (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 partitionedas $L(A_1) \sqcup \ldots \sqcup L(A_t)$ and every $L(A_i)$ is orderable inthis 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 beproduced by a bounded-delay algorithm: specifically, the algorithm runs in asuitable pointer machine model, and produces a sequence of bounded-length editscripts 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 onlyallowing the edit operations push and pop at the beginning andend 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 wordsand the number of classes of the partition, it is NP-hard in the input DFA $A$to decide if $L(A)$ is orderable in this sense, already for finite languages. Last, we study the model where push-pop edits are only allowed at the end ofthe word, corresponding to a case where the word is maintained on a stack.We show that these operations are strictly weaker and that the slenderlanguages are precisely those that can be partitioned into finitely manylanguages that are orderable in this sense. For the slender languages, we can againcharacterize the minimal number of languages in the partition, and achievebounded-delay enumeration.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Projet ANR :
Commentaire :
STACS'2023
Collections :
Source :
Fichiers
- document
- Accès libre
- Accéder au document
- enumerating.pdf
- Accès libre
- Accéder au document
- 2209.14878
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- enumerating.pdf
- Accès libre
- Accéder au document