BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:ed364765-1536-44ad-a79b-b293077538f7
X-WR-CALNAME:[M2F] Antoine Amarilli
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20251026T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20241027T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20230326T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20240331T020000
RDATE:20250330T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:ed364765-1536-44ad-a79b-b293077538f7
DTSTAMP:20260522T194824Z
CLASS:PUBLIC
DESCRIPTION:**Enumerating Regular Languages in Bounded Delay**\n\nWe study 
 the task\, for a given language L\, of enumerating the (generally infinite
 ) sequence of its words\, without repetitions\, while bounding the delay b
 etween 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 writ
 ing out the word from scratch. \nIn particular\, this witnesses that the l
 anguage is orderable\, i.e.\, we can write its words as an infinite sequen
 ce such that the Levenshtein edit distance between any two consecutive wor
 ds 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.
 \n\nWe characterize which regular languages are enumerable in this sense\,
  and show that this can be decided in PTIME in an input deterministic fini
 te automaton (DFA) for the language. In fact\, we show that\, given a DFA 
 A\, we can compute in PTIME automata A1\,…\,At such that L(A) is partition
 ed 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.\, we cannot partiti
 on L(A) into less than t orderable languages.\n\nIn the case where L(A) is
  orderable (i.e.\, t=1)\, we show that the ordering can be produced by a b
 ounded-delay algorithm: specifically\, the algorithm runs in a suitable po
 inter machine model\, and produces a sequence of bounded-length edit scrip
 ts 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 a
 chieve this while only allowing the edit operations push and pop at the be
 ginning and end of the word\, which implies that the word can in fact be m
 aintained in a double-ended queue.
DTSTART;TZID=Europe/Paris:20240305T140000
DTEND;TZID=Europe/Paris:20240305T150000
LOCATION:LaBRI
SEQUENCE:0
SUMMARY:[M2F] Antoine Amarilli
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
