Deterministic recognizability of picture languages with Wang automata
Violetta Lonati, Matteo Pradella
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-ways 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.
Full Text: PDF PostScript