Affiliations: [a] Dip. di Informatica, Università di Salerno, V. G. Paolo II, 132, I-84084 Fisciano (SA), Italy. manselmo@unisa.it | [b] Dip. di Matematica, Università Roma “Tor Vergata”, Via della Ricerca Scientifica, 00133 Roma, Italy. giammarr@mat.uniroma2.it | [c] Dip. Matematica e Informatica, Università di Catania, Viale Andrea Doria 6/a, 95125 Catania, Italy. madonia@dmi.unict.it
Correspondence:
[†]
Address for correspondence: Dip. di Informatica, Università di Salerno, V. G. Paolo II, 132, I-84084 Fisciano (SA), Italy
Note: [*] Partially supported by INdAM-GNCS Projects 2018-2019, FARB Project ORSA175982 of University of Salerno and CREAMS Project of University of Catania. The second author acknowledges the MIUR Excellence Department Project awarded to the Department of Mathematics, University of Rome Tor Vergata, CUP E83C18000100006
Abstract: We introduce the two-dimensional rational automata (RA) to recognize languages of pictures, as an extension of the finite automata for strings. A RA processes a picture column by column changing its state. The states are columns of symbols, too. The transition function is realized by a transducer. We prove that RA recognize the family REC of languages recognized by tiling systems. Moreover, RA provide a uniform setting for a lot of important notions, techniques and results presented in the last decades for recognizable two-dimensional languages. The model is also very flexible. In fact, there can be imposed restrictions or added features to easily interesting new classes and examples or to capture known families of languages.
