Comparison-free polyregular functions

Prelegent(ci)

Lê Thành Dũng (Tito) Nguyễn

Afiliacja

LIPN (Paris Nord)

Termin

16 czerwca 2021 14:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium „Teoria automatów”

---

We introduce a new automata-theoretic class of string-to-string functions with polynomial growth. Several equivalent definitions are provided: a machine model which is a restricted variant of pebble transducers, and a few inductive definitions that close the class of regular functions under certain operations. As their name suggests, these "comparison-free polyregular functions" form a subclass of polyregular functions; we prove that the inclusion is strict. We also show that they are incomparable with HDT0L transductions, closed under usual function composition – but not under a certain "map" combinator – and satisfy a comparison-free version of the pebble minimization theorem. This talk is based on a joint work with Pierre Pradic (and the fictional author Camille Noûs) [1]) accepted at ICALP 2021. If time allows, I will also present some related results on integer sequences that did not appear in the paper. [1]: https://hal.archives-ouvertes.fr/hal-02986228

---