Regularity reflection for higher-order tree transducers and its consequences

Prelegent(ci)

Nguyễn Lê Thành Dũng

Afiliacja

CNRS, LIS, Aix-Marseille Université

Język referatu

angielski

Termin

28 października 2026 14:15

Pokój

p. 5440

Tytuł w języku polskim

Regularity reflection for higher-order tree transducers and its consequences

Seminarium

Seminarium „Teoria automatów”

First, I will explain why the inverse image of a regular tree language by a higher-order tree transducer — an automaton that computes a tree-to-tree function by manipulating simply typed λ-terms — is itself a regular tree language. This "regularity reflection" property is therefore inherited by any device that can be translated to a higher-order tree transducer. I will give such a translation (j.w.w. Luc Dartois & Charles Peyrat) for tree-to-tree Hennie machines. Regularity reflection for the latter has two consequences, via recent work of Colcombet, Lhote & Ohlmann (ICALP 2026):
* alternating linear-time Turing machine recognize only regular languages, refuting a conjecture from Niwiński's lecture notes on computational complexity;
* MSO is decidable for automatic words, answering positively a two-decades-old conjecture from Bárány's PhD thesis.