We introduce a model of automaton for picture language recognition which is based on tiles and is called Wang automaton, since its description relies on the notation of Wang systems. 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. We prove that 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 consider a very natural notion of determinism for Wang automata, and study the resulting class, comparing it with other deterministic classes considered in the literature, like DREC and Snake-DREC.
Picture recognizability with automata based on Wang tiles / V. Lonati, M. Pradella - In: SOFSEM 2010 : theory and practice of computer science : 36th Conference on current trends in theory and practice of computer science, Spindleruv Mlýn, Czech Republic, January 23-29, 2010 : proceedings / / [a cura di] J. van Leeuwen [et al.]. - Berlin : Springer, 2010. - ISBN 9783642112652. - pp. 576-587 (( Intervento presentato al 36. convegno International Conference on Current trends in Theory and Practice of Computer Sciences (SOFSEM 2010) tenutosi a Špindleruv Mlýn, Czech Republic. nel 2010 [10.1007/978-3-642-11266-9_48].
Picture recognizability with automata based on Wang tiles.
V. LonatiPrimo
;
2010
Abstract
We introduce a model of automaton for picture language recognition which is based on tiles and is called Wang automaton, since its description relies on the notation of Wang systems. 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. We prove that 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 consider a very natural notion of determinism for Wang automata, and study the resulting class, comparing it with other deterministic classes considered in the literature, like DREC and Snake-DREC.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.