|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc020403,
author = {Lucio de Prophetis and Stefano Varricchio},
title = {Recognizability of Rectangular Pictures by Wang Systems},
journal = jalc,
year = 1997,
volume = 2,
number = 4,
pages = {269--288},
keywords = {automata, picture languages, tilings},
abstract = {In this paper we introduce labelled Wang tiles (LWT), that
are a generalization of Wang tiles. We use LWT to introduce
Wang systems (WS), a new formalism to recognize picture
languages. We prove that the family of picture languages
defined by Wang systems coincides with the family of picture
languages recognized by tiling systems. We also consider
unary picture languages, i.e. picture languages over an
alphabet of one symbol, and define a natural bijection
between pictures and elements of $\{a\}^* \times \{b\}^*$.
Then we prove that any rational relation of
$\{a\}^* \times \{b\}^*$ can be obtained as the image of a
recognizable picture language. Finally, we prove that the
family of star-free (unary) picture language is included
in ${\cal R}\mbox{\it at} (\{a\}^* \times \{b\}^*)$.}
}
@string{jalc = "Journal of Automata, Languages and Combinatorics"}