Narrow Results

In a recent paper, Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with the usual acceptance conditions, such as the Büchi and Muller ones, firstly used for infinite words. The authors asked for comparing the tiling system acceptance with an acceptance of pictures row by row using an automaton model over ordinal words of length ω². We give in this paper a solution to this problem, showing that all languages of infinite pictures which are accepted row by row by Büchi or Choueka automata reading words of length ω² are Büchi recognized by a finite tiling system, but the converse is not true. We give also the answer to two other questions which were raised by Altenbernd, Thomas and Wöhrle, showing that it is undecidable whether a Büchi recognizable language of infinite pictures is E-recognizable (respectively, A-recognizable).

Tiling recognizable two-dimensional languages, also known as REC, generalize recognizable string languages to two dimensions and share with them several theoretical properties. Nevertheless family REC is not closed under complementation and this implies that it is intrinsically non-deterministic. We consider different notions of unambiguity and determinism and the corresponding REC subclasses: they define a hierarchy inside REC. We show that some definitions of unambiguity are equivalent to particular notions of determinism and therefore the corresponding classes have linear parsing algorithms and are closed under complementation.

We present a new model of a two-dimensional computing device called restarting tiling automaton. The automaton defines a set of tile-rewriting, weight-reducing rules and a scanning strategy by which a tile to rewrite is being searched. We investigate properties of the induced families of picture languages. Special attention is paid to picture languages that can be accepted independently of the scanning strategy. We show that this family strictly includes REC and exhibits similar closure properties. Moreover, we prove that its intersection with the set of one-row languages coincides with the regular languages.

In this paper we consider hexagonal arrays on triangular grids and introduce hexagonal local picture languages and hexagonal tiling systems defining hexagonal recognizable picture languages, motivated by an analogous study of rectangular arrays by Giammarresi and Restivo. We also introduce hexagonal Wang tiles to define hexagonal Wang systems (HWS) as a formalism to describe hexagonal picture languages. It is noticed that the family of hexagonal picture languages defined by hexagonal Wang systems and the family recognized by hexagonal tiling systems coincide. Analogous to hv-domino systems describing rectangular arrays, we define xyz-domino systems and prove that recognizable hexagonal picture languages are characterized as projections of xyz-local picture languages.