On a complete set of operations for factorizing codes

Dipartimento di Informatica e Applicazioni, Università di Salerno, 84081 Baronissi (SA), Italy; defelice@dia.unisa.it

Received: 20 April 2004
Accepted: 15 February 2005

Abstract

It is known that the class of factorizing codes, i.e., codes satisfying the factorization conjecture formulated by Schützenberger, is closed under two operations: the classical composition of codes and substitution of codes. A natural question which arises is whether a finite set O of operations exists such that each factorizing code can be obtained by using the operations in O and starting with prefix or suffix codes. O is named here a complete set of operations (for factorizing codes). We show that composition and substitution are not enough in order to obtain a complete set. Indeed, we exhibit a factorizing code over a two-letter alphabet A = {a,b}, precisely a 3-code, which cannot be obtained by decomposition or substitution.