
doi: 10.46298/dmtcs.511
handle: 20.500.14243/50151 , 2434/148904 , 11311/617506
special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications 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.
unambiguity, tiling system, tiling systems, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], determinism, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 2d language, wang systems, picture language, picture languages ; 2D languages ; tiling systems ; Wang systems ; determinism ; ambiguity, 4-way automata, QA1-939, Wang systems, online tessellation acceptors, Mathematics, 2D language
unambiguity, tiling system, tiling systems, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], determinism, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 2d language, wang systems, picture language, picture languages ; 2D languages ; tiling systems ; Wang systems ; determinism ; ambiguity, 4-way automata, QA1-939, Wang systems, online tessellation acceptors, Mathematics, 2D language
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
