Two-way Automata and Regular Languages of Overlapping Tiles

Article type: Research Article

Authors: Dicky, Anne^a | Janin, David^{a; *}

Affiliations: [a] Université de Bordeaux, LaBRI UMR 5800, 351, cours de la Libération, F-33405 Talence, France. dicky@labri.fr, janin@labri.fr

Correspondence: [*] Address for correspondence: Université de Bordeaux, LaBRI UMR 5800, 351, cours de la Libération, F-33405 Talence, France.

Abstract: We consider classes of languages of overlapping tiles, i.e., subsets of the McAlister monoid: the class REG of languages definable by Kleene’s regular expressions, the class MSO of languages definable by formulas of monadic second-order logic, and the class REC of languages definable by morphisms into finite monoids. By extending the semantics of finite-state two-way automata (possibly with pebbles) from languages of words to languages of tiles, we obtain a complete characterization of the classes REG and MSO. In particular, we show that adding pebbles strictly increases the expressive power of two-way automata recognizing languages of tiles, but the hierarchy induced by the number of allowed pebbles collapses to level one.

Keywords: two-way automata, word languages, overlapping tile languages, regular languages, McAlister inverse monoid

DOI: 10.3233/FI-2015-1278

Journal: Fundamenta Informaticae, vol. 141, no. 4, pp. 311-343, 2015