Two-way Automata and Regular Languages of Overlapping Tiles

被引:0
作者
Dicky, Anne [1 ]
Janin, David [1 ]
机构
[1] Univ Bordeaux, LaBRI UMR 5800, F-33405 Talence, France
关键词
two-way automata; word languages; overlapping tile languages; regular languages; McAlister inverse monoid; INVERSE; REDUCTION;
D O I
10.3233/FI-2015-1278
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页码:310 / 342
页数:33
相关论文
共 50 条
[1]   TRANSLATION FROM CLASSICAL TWO-WAY AUTOMATA TO PEBBLE TWO-WAY AUTOMATA [J].
Geffert, Viliam ;
Istonova, L'ubomira .
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2010, 44 (04) :507-523
[2]   Alternation in two-way finite automata [J].
Kapoutsis, Christos ;
Zakzok, Mohammad .
THEORETICAL COMPUTER SCIENCE, 2021, 870 (870) :75-102
[3]   On the state complexity of operations on two-way finite automata [J].
Jiraskova, Galina ;
Okhotin, Alexander .
INFORMATION AND COMPUTATION, 2017, 253 :36-63
[4]   Two-Way Automata in Coq [J].
Doczkal, Christian ;
Smolka, Gert .
INTERACTIVE THEOREM PROVING (ITP 2016), 2016, 9807 :151-166
[5]   Normality and two-way automata [J].
Carton, Olivier ;
Heiber, Pablo Ariel .
INFORMATION AND COMPUTATION, 2015, 241 :264-276
[6]   TWO-WAY REPRESENTATIONS AND WEIGHTED AUTOMATA [J].
Lombardy, Sylvain .
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2016, 50 (04) :331-350
[7]   Alternation in two-way finite automata [J].
Konstantinidis, Stavros ;
Moreira, Nelma ;
Reis, Rogerio .
THEORETICAL COMPUTER SCIENCE, 2021, 870 :103-120
[8]   Two-way automata making choices only at the endmarkers [J].
Geffert, Viliam ;
Guillon, Bruno ;
Pighizzini, Giovanni .
INFORMATION AND COMPUTATION, 2014, 239 :71-86
[9]   On the transformation of two-way finite automata to unambiguous finite automata [J].
Petrov, Semyon ;
Okhotin, Alexander .
INFORMATION AND COMPUTATION, 2023, 295
[10]   On Determinism and Unambiguity of Weighted Two-Way Automata [J].
Carnino, Vincent ;
Lombardy, Sylvain .
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2015, 26 (08) :1127-1146