Relations on free monoids, their independent sets, and codes¹

¹This research was supported by the Natural Science and Engineering Research Council of Canada, Grant OGP0000243.

Abstract

Many classes of codes can be characterized as families of antichains with respect to partial orders on the free monoid or, in more general terms, as families of independent sets with respect to some binary relations. In this paper we investigate the general properties of this connection between families of sets and binary relations. This theory provides a framework in which known results about codes can be expressed elegantly and in which several new results are derived. Moreover, this theory can be generalized to relations of arbitrary finite arity in a very natural fashion. This allows us, for instance, to prove new hierarchy results. More importantly, however, this theory provides a new and profound insight into the mechanisms by which classes of codes are defined.

Keywords:

• Code
• relation
• combinatorics of words

C.R. Codes:

• E.4
• F.4.3

¹This research was supported by the Natural Science and Engineering Research Council of Canada, Grant OGP0000243.

¹This research was supported by the Natural Science and Engineering Research Council of Canada, Grant OGP0000243.

Notes

¹This research was supported by the Natural Science and Engineering Research Council of Canada, Grant OGP0000243.