Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
The Spectra of Words
verfasst von : Robin Milner
Erschienen in: Processes, Terms and Cycles: Steps on the Road to Infinity
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The
k
-spectrum of a word is the multiset of its non-contiguous subwords of length
k
. For given
k
, how small can
n
be for a pair of different words of length
n
to exist, with equal
k
- spectra? From the Thue-Morse word we find that
n
is at most 2
k
. The construction of this paper decreases this upper bound to
θ
k
, where
$\bumpeq$
is the golden ratio; the construction was found, though not published, over thirty years ago. Recently the bound has been further reduced, but remains considerably greater than the greatest known lower bound.