Brick codes: families, properties, relations

Abstract

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 Schiitzenberger'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.

Keywords:

• Multidimensional Codes
• Brick Codes
• Polyominoes
• Tilings
• Codicity