The Meet Operation in the Lattice of Codes

V. BRUYERE, D. DERENCOURT, M. LATTEUX

IBP-Litp 1996/10: Rapport de Recherche Litp / Litp research reports
16 pages - Février/February 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: The Meet Operation in the Lattice of Codes

Résumé : On étudie les propriétés de la borne inférieure X ‹ Y de deux codes rationnels X et Y , définie comme la base du monoïde libre X * « Y *. Nous donnons un contre-exemple à la conjecture de R. König affirmant que si X et Y sont deux codes maximaux rationnels, alors que le code X ‹ Y est aussi maximal. We donnons une caractérisation combinatoire des codes pour lesquels la conjecture est vraie. Nous montrons aussi que tout code rationnel (maximal ou pas) peut s'obtenir comme la borne inférieure X ‹ Y de de deux codes rationnaux maximaux.

Abstract : We study properties of the meet of two rational codes X and Y , defined as the base of the free monoid X * « Y *. We disprove R. König's conjecture stating that if X and Y are two rational maximal codes, then their meet is also maximal. We give a combinatorial characterization of codes for wich the conjecture is true. We also show that any rational (maximal or not) code is the meet of two rational maximal codes.

Publications internes Litp 1996 / Litp research reports 1996