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.
Anselmo, M., Giammarresi, D., Madonia, M. (2013). Two-Dimensional Rational Automata: A Bridge Unifying One- and Two-Dimensional Language Theory. In SOFSEM 2013: Theory and Practice of Computer Science (pp. 133-145). Springer, Heidelberg [10.1007/978-3-642-35843-2_13].
Two-Dimensional Rational Automata: A Bridge Unifying One- and Two-Dimensional Language Theory
GIAMMARRESI, DORA;
2013-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
