The Spectra of Words

Robin Milner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 2k . The construction of this paper decreases this upper bound to θk , where ≏ 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.

Original languageEnglish
Title of host publicationProcesses, Terms and Cycles: Steps on the Road to Infinity
Subtitle of host publicationEssays Dedicated to Jan Willem Klop on the Occasion of His 60th Birthday
EditorsAart Middeldorp, Vincent Oostrom, Femke Raamsdonk, Roel Vrijer
PublisherSpringer Berlin Heidelberg
Pages1-5
Number of pages5
Volume3838
ISBN (Electronic)978-3-540-32425-6
ISBN (Print)978-3-540-30911-6
DOIs
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg

Fingerprint Dive into the research topics of 'The Spectra of Words'. Together they form a unique fingerprint.

Cite this