Two-Dimensional Rational Automata: A Bridge Unifying One- and Two-Dimensional Language Theory

摘要

We define two-dimensional rational automata for pictures as an extension of classical finite automata for strings. They are obtained replacing the finite relation computed by the transition function with a rational relation computed by a transducer. The model provides a uniform setting for the most important notions, techniques and results presented in the last decades for recognizable two-dimensional languages, and establishes new connections between one- and two- dimensional language theory.