Comparison-free polyregular functions

Speaker(s)

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

Affiliation

LIPN (Paris Nord)

Date

June 16, 2021, 2:15 p.m.

Information about the event

online

Seminar

Seminar Automata Theory

---

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

---