Two-way Automata and Regular Languages of Overlapping Tiles | Zendy

Anne Dicky | Zendy; David Janin | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Two-way Automata and Regular Languages of Overlapping Tiles

Author(s) -

Anne Dicky,

David Janin

Publication year - 2015

Publication title -

fundamenta informaticae

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.311

H-Index - 67

eISSN - 1875-8681

pISSN - 0169-2968

DOI - 10.3233/fi-2015-1278

Subject(s) - automaton , computer science , regular language , programming language , nondeterministic finite automaton , theoretical computer science , automata theory , mathematics , arithmetic , discrete mathematics

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 au- tomata (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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research