Two-way automata and transducers with planar behaviours are aperiodic
Lê Thành Dũng Nguyễn, Camille Noûs, Cécilia Pradic · arXiv (Cornell University) · 2023
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-free languages and first-order transductions.