We present a model of automaton for picture language recognition, calledWang 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.

Deterministic recognizability of picture languages with Wang automata / V. Lonati, M. Pradella. - In: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE. - ISSN 1462-7264. - 12:4(2010), pp. 73-94.

Deterministic recognizability of picture languages with Wang automata

V. Lonati;
2010

Abstract

We present a model of automaton for picture language recognition, calledWang 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.
picture languages ; 2D languages ; tiling systems ; Wang systems ; determinism ; ambiguity
Settore INF/01 - Informatica
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1471
Article (author)
File in questo prodotto:
File Dimensione Formato  
1471-5709-1-PB.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 258.97 kB
Formato Adobe PDF
258.97 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/148904
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 6
social impact