Regularity reflection for higher-order tree transducers and its consequences

Speaker(s)

Nguyễn Lê Thành Dũng

Affiliation

CNRS, LIS, Aix-Marseille Université

Language of the talk

English

Date

Oct. 28, 2026, 2:15 p.m.

Room

room 5440

Title in Polish

Regularity reflection for higher-order tree transducers and its consequences

Seminar

Seminar Automata Theory

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.