Two-way automata and transducers with planar behaviours are aperiodic

Abstract

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.

18 pages, DMTCS submission

Cited by in corpus (1)

• Implicit automata in λ-calculi III: affine planar string-to-string functions