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

来源：

FUNDAMENTA INFORMATICAE | 2015年 / 141卷 / 04期

关键词：

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 条

[41] Best linear unbiased prediction in the two-way error components model with AR(1) error processes [J].

Kelik, Serge Tayim ;

Soh, Patrice Takam ;

Kouassi, Eugene ;

Fotso, Simeon .

COMMUNICATIONS IN STATISTICS-SIMULATION AND COMPUTATION, 2025,

[42] Seismic effectiveness of top-story mass dampers for inelastic two-way asymmetric-plan buildings [J].

Lin, Jui-Liang .

ENGINEERING STRUCTURES, 2018, 161 :118-133

[43] Graphene-crosslinked two-way reversible shape memory polyurethane nanocomposites with enhanced mechanical and electrical properties [J].

Jiu, Hongfang ;

Jiao, Hongqian ;

Zhang, Lixin ;

Zhang, Shaomei ;

Zhao, Yanan .

JOURNAL OF MATERIALS SCIENCE-MATERIALS IN ELECTRONICS, 2016, 27 (10) :10720-10728

[44] A Comparison of Two-Way (Chemical and Thermal) Synthesis and Characterization of Graphene Oxide (GO) and Reduced Graphene Oxide (rGO) [J].

Inam, Ul Haq ;

Abdul, Waheed Anwar ;

Zeeshan, Abdullah ;

Abdul, Waheed ;

Zunair, Arslan ;

Usman, Ilyas .

JOURNAL OF NANO RESEARCH, 2024, 85 :53-62

[45] Analysis of wake induced vibration of a coupled circular cylinder-piezoelectric using two-way fluid structural interaction [J].

Derakhshandeh, Javad Farrokhi .

APPLIED OCEAN RESEARCH, 2022, 121

[46] Bi-directional coupled tuned mass dampers for the seismic response control of two-way asymmetric-plan buildings [J].

Lin, Jui-Liang ;

Tsai, Keh-Chyuan ;

Yu, Yi-Jer .

EARTHQUAKE ENGINEERING & STRUCTURAL DYNAMICS, 2011, 40 (06) :675-690

[47] Top-story mass dampers for seismic control of the first triplet of vibration modes of two-way asymmetric-plan buildings [J].

Lin, Jui-Liang .

JOURNAL OF VIBRATION AND CONTROL, 2017, 23 (18) :2962-2976

[48] Numerical simulation of the electromagnetic torques of PMSM with two-way magneto-mechanical coupling and nonuniform spline clearance in electric submersible pumping wells [J].

Liu, Xin-Fu ;

Liu, Chun-Hua ;

Zheng, Ying ;

Yu, Ji-Fei ;

Zhou, Wei ;

Wang, Meng-Xiao ;

Liu, Peng ;

Zhou, Yi-Fei .

PETROLEUM SCIENCE, 2024, 21 (06) :4417-4426

[49] Bi-Directional Coupled Tuned Mass Dampers for Two-Way Asymmetric-Plan Buildings under Bi-Directional Ground Excitations [J].

Lin, Jui-Liang ;

Tsai, Keh-Chyuan ;

Yu, Yi-Jer .

PROCEEDINGS OF THE 8TH INTERNATIONAL CONFERENCE ON STRUCTURAL DYNAMICS, EURODYN 2011, 2011, :1886-1891

[50] Two-way rushing travel: Cathodic-anodic coupling of Bi2O3-SnO@CuO nanowires, a bifunctional catalyst with excellent CO2RR and MOR performance for the efficient production of formate [J].

Tang, Zheng ;

Wang, Yu ;

Qian, Wenxuan ;

Piao, Zhe ;

Wang, Honggui ;

Zhang, Ya .

JOURNAL OF COLLOID AND INTERFACE SCIENCE, 2023, 652 :1653-1664

← 1 2 3 4 5 →