5 citations · 19 across the 10 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.LO2023★ 1 cited
Syntactically and semantically regular languages of lambda-terms coincide through logical relations
Vincent Moreau, Lê Thành Dũng Nguyên
A fundamental theme in automata theory is regular languages of words and trees, and their many equivalent definitions. Salvati has proposed a generalization to regular languages of…
cs.FL2023★ 2 cited
Two-way automata and transducers with planar behaviours are aperiodic
Lê Thành Dũng Nguyên, Camille Noûs, Cécilia Pradic
We consider a notion of planarity for two-way finite automata and transducers, inspired by Temperley-Lieb monoids of planar diagrams. We show that this restriction captures star-fr…
cs.LO2023★ 1 cited
Simply typed convertibility is TOWER-complete even for safe lambda-terms
Lê Thành Dũng Nguyên
We consider the following decision problem: given two simply typed -terms, are they -convertible? Equivalently, do they have the same normal form? It is famously non-elementa…