The concept of determinism, while clear and well assessed for string languages, is still matter of research as far as picture languages are concerned. We introduce here a new kind of determinism, called snake, based on the boustrophedonic scanning strategy, that is a natural scanning strategy used by many algorithms on 2D arrays and pictures. We consider a snake-deterministic variant of tiling systems, which defines the so-called Snake-DREC class of languages. Snake-DREC properly extends the more traditional approach of diagonal-based determinism, used e.g. by deterministic tiling systems, and by online tessellation automata. Our main result is showing that the concept of snake-determinism of tiles coincides with row (or column) unambiguity.

Snake-Deterministic Tiling Systems / V. Lonati, M. Pradella (LECTURE NOTES IN COMPUTER SCIENCE). - In: Mathematical Foundations of Computer Science / [a cura di] R. Královic, D. Niwinski. - Berlin : Springer Berlin / Heidelberg, 2009 Aug 19. - ISBN 9783642038150. - pp. 549-560 (( Intervento presentato al 34. convegno International Symposium tenutosi a Novy Smokovec, High Tatras (Slovakia) nel 2009 [10.1007/978-3-642-03816-7_47].

Snake-Deterministic Tiling Systems

V. Lonati
Primo
;
2009

Abstract

The concept of determinism, while clear and well assessed for string languages, is still matter of research as far as picture languages are concerned. We introduce here a new kind of determinism, called snake, based on the boustrophedonic scanning strategy, that is a natural scanning strategy used by many algorithms on 2D arrays and pictures. We consider a snake-deterministic variant of tiling systems, which defines the so-called Snake-DREC class of languages. Snake-DREC properly extends the more traditional approach of diagonal-based determinism, used e.g. by deterministic tiling systems, and by online tessellation automata. Our main result is showing that the concept of snake-determinism of tiles coincides with row (or column) unambiguity.
picture language ; 2D language ; tiling systems ; online tessellation automata ; determinism
Settore INF/01 - Informatica
19-ago-2009
EATCS
Comenius University Faculty of Mathematics, Physics & Informatics
http://www.springerlink.com/content/p6k2735034578h26/
Book Part (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
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: https://hdl.handle.net/2434/67129
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 10
social impact