Two-way automata and transducers with planar behaviours are aperiodic

Autor:	Nguyên, Lê Thành Dũng, Noûs, Camille, Pradic, Cécilia
Rok vydání:	2023
Předmět:	Computer Science - Formal Languages and Automata Theory
Druh dokumentu:	Working Paper
Popis:	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. Comment: 18 pages, DMTCS submission
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2307.11057 Zobrazit plný text záznamu View this record from Arxiv