Violetta Lonati ; Matteo Pradella - Deterministic recognizability of picture languages with Wang automata

dmtcs:511 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 4 - https://doi.org/10.46298/dmtcs.511
Deterministic recognizability of picture languages with Wang automataArticle

Authors: Violetta Lonati ORCID1; Matteo Pradella ORCID2

  • 1 Dipartimento di Scienze dell'Informazione [Milano]
  • 2 Istituto di Elettronica e di Ingegneria dell'Informazione e delle Telecomunicazioni

We present a model of automaton for picture language recognition, called Wang automaton, which is based on labeled Wang tiles. Wang automata combine features of both online tessellation acceptors and 4-way automata: as in online tessellation acceptors, computation assigns states to each picture position; as in 4-way automata, the input head visits the picture moving from one pixel to an adjacent one, according to some scanning strategy. Wang automata recognize the class REC, i.e. they are equivalent to tiling systems or online tessellation acceptors, and hence strictly more powerful than 4-way automata. We also introduce a natural notion of determinism for Wang automata, and study the resulting class, extending the more traditional approach of diagonal-based determinism, used e. g. by deterministic tiling systems. In particular, we prove that the concept of row (or column) ambiguity defines the class of languages recognized by Wang automata directed by boustrophedonic scanning strategies.


Volume: Vol. 12 no. 4
Published on: January 1, 2010
Imported on: March 26, 2015
Keywords: picture language,2D language,tiling systems,4-way automata,online tessellation acceptors,Wang systems,determinism,unambiguity,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 253 times.
This article's PDF has been downloaded 212 times.