CHARACTERIZATION OF A WORD BY ITS SUBWORDS

Abstract

We consider what is the amount of subwords of a word needed to completely determine the word. More precisely, we study the maximal length such that all words of this length can be uniquely determined by its subwords of a fixed length. The set of subwords of a fixed length is called a spectrum. Four types of spectrums are analyzed: sparse, factor, sparse with multiplicity and factor with multiplicity. We also study the equivalence between the proper spectrum (subwords of a fixed length) and full spectrum (subwords at most of a fixed length) for each case. In all cases except sparse with multiplicity we give a precise answer. The results about factors and about the equivalence between the proper and full spectrums are new. TUCS Research Group