Nie jesteś zalogowany | Zaloguj się

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