Détail de la notice
Titre du Document
Brick codes : Families, properties, relations
Auteur(s)
MOCZURAD W.
Résumé
Variable-length word codes, i.e., sets of words such that every word generated has a unique factorization over the set, are a common object of study. Here we are interested in multidimensional words and codes. The multidimensional words are in fact labelled shapes-or labelled polyominoes - and we call them bricks. We begin with basic definitions and properties related to codicity, including a brick version of the well-known Schützenberger's theorem. We present several important families of brick codes. We then investigate which families of brick codes can be defined with n-argument relations (bounded testability), showing that some of the important non-trivial families do not admit such characterization. We also analyze the structure of the set of relations that do define families of brick codes. We introduce the notion of a chromatic number which is the minimal number of labels necessary to obtain a code from a given set of bricks, and we study its behaviour with respect to the size and granularity of brick sets.
Editeur
Taylor and Francis
Identifiant
ISSN : 0020-7160 CODEN : IJCMAT
Source
International journal of computer mathematics A. 2000, vol. 74, n° 2, pp. 133-150 [bibl. : 14 ref.]
Langue
Anglais
Pour les membres de la communauté du CNRS, ce document est autorisé à la reproduction à titre gratuit.
Pour les membres des communautés hors CNRS, la reproduction de ce document à titre onéreux sera fournie sous réserve d’autorisation du Centre Français d’exploitation du droit de Copie.

Pour bénéficier de nos services (strictement destinés aux membres de la communauté CNRS (Centre National de la Recherche Scientifique), de l'ESR français (Enseignement Supérieur et Recherche), et du secteur public français & étranger) :