Deterministic recognizability of picture languages with Wang automata

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (4), pp.73-94
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990448
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:37:21
Dernière modification le : mercredi 29 novembre 2017 - 10:26:18
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:14:54

Fichier

1471-5709-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990448, version 1

Collections

Citation

Violetta Lonati, Matteo Pradella. Deterministic recognizability of picture languages with Wang automata. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (4), pp.73-94. 〈hal-00990448〉

Partager

Métriques

Consultations de la notice

94

Téléchargements de fichiers

233