Two-way automata and transducers with planar behaviours are aperiodic

Finite automata and their decision problems

Michael O. Rabin and Dana S. Scott · 1959

Earlier work this paper cites.

The reduction of two-way automata to one-way automata

John C. Shepherdson · 1959

Earlier work this paper cites.

On relations defined by generalized finite automata

Calvin C. Elgot and Jorge E. Mezei · 1965

Earlier work this paper cites.

Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines

Kenneth Krohn and John Rhodes · 1965

Earlier work this paper cites.

Inherently nonplanar automata

Ronald V. Book and Ashok K. Chandra · 1976

Earlier work this paper cites.

Concatenation of inputs in a two-way automaton

Jean-Camille Birget · 1989

Earlier work this paper cites.

An invariant of regular isotopy

Louis Kauffman · 1990

Earlier work this paper cites.

Divisors of semigroups of order-preserving mappings on a finite chain

Peter M. Higgins · 1995

Earlier work this paper cites.

Graphs on Surfaces

Bojan Mohar and Carsten Thomassen · 2001

Earlier work this paper cites.

A categorical framework for finite state machines

Peter Hines · 2003

Earlier work this paper cites.

Synchronizing monotonic automata

Dimitry S. Ananichev and Mikhail V. Volkov · 2004

Earlier work this paper cites.

Temperley-Lieb Algebras as two-way automata

Peter Hines · 2006

Earlier work this paper cites.

Ideal structure of the kauffman and related monoids

Kwok Wai Lau and D. G. FitzGerald · 2006

Cited alongside, same era.

Temperley–Lieb Algebra: From Knot Theory to Logic and Computation via Quantum Mechanics

Samson Abramsky · 2007

Cited alongside, same era.

Tree-walking automata do not recognize all regular languages

Mikołaj Bojańczyk and Thomas Colcombet · 2008

Cited alongside, same era.

Attribute grammars and categorical semantics

Shin-ya Katsumata · 2008

Cited alongside, same era.

Expressiveness of streaming string transducers

Rajeev Alur and Pavol Černý · 2010

Cited alongside, same era.

Musings around the geometry of interaction, and coherence

Jean Goubault-Larrecq · 2010

Cited alongside, same era.

Aperiodic String Transducers

Luc Dartois, Ismaël Jecker, and Pierre-Alain Reynier · 2018

Later among the works it cites.

First-order logic and aperiodic languages: a revisionist history

Original

Howard Straubing · 2018

Later among the works it cites.

Decidability of regular language genus computation

Guillaume Bonfante and Florian L. Deloup · 2019

Later among the works it cites.

On the Expressivity of Linear Recursion Schemes

Pierre Clairambault and Andrzej S. Murawski · 2019

Later among the works it cites.

The Many Facets of String Transducers

Anca Muscholl and Gabriele Puppis · 2019

Later among the works it cites.

Implicit automata in typed λ \lambda -calculi I: aperiodicity in a non-commutative logic

Lê Thành Dũng Nguyễn and Cécilia Pradic · 2020