Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2015

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Two-way Automata and Regular Languages of Overlapping Tiles

Dicky A., Janin D.

Fundamenta Informaticae

2015

Vol. 141, nr 4

311--343

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.