The Spectra of Words

Robin Milner

doi:10.1007/11601548_1

The Spectra of Words

Robin Milner

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 2^k . 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 language	English
Title of host publication	Processes, Terms and Cycles: Steps on the Road to Infinity
Subtitle of host publication	Essays Dedicated to Jan Willem Klop on the Occasion of His 60th Birthday
Editors	Aart Middeldorp, Vincent Oostrom, Femke Raamsdonk, Roel Vrijer
Publisher	Springer Berlin Heidelberg
Pages	1-5
Number of pages	5
Volume	3838
ISBN (Electronic)	978-3-540-32425-6
ISBN (Print)	978-3-540-30911-6
DOIs	https://doi.org/10.1007/11601548_1
Publication status	Published - 2005

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg

Access to Document

10.1007/11601548_1

http://link.springer.com/chapter/10.1007%2F11601548_1

Cite this

@inproceedings{adfc0cc493a847b68e6124524fd23e18,

title = "The Spectra of Words",

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.",

author = "Robin Milner",

year = "2005",

doi = "10.1007/11601548_1",

language = "English",

isbn = "978-3-540-30911-6",

volume = "3838",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "1--5",

editor = "Aart Middeldorp and Vincent Oostrom and Femke Raamsdonk and Roel Vrijer",

booktitle = "Processes, Terms and Cycles: Steps on the Road to Infinity",

}

The Spectra of Words. / Milner, Robin.

Processes, Terms and Cycles: Steps on the Road to Infinity: Essays Dedicated to Jan Willem Klop on the Occasion of His 60th Birthday. ed. / Aart Middeldorp; Vincent Oostrom; Femke Raamsdonk; Roel Vrijer. Vol. 3838 Springer Berlin Heidelberg, 2005. p. 1-5 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - The Spectra of Words

AU - Milner, Robin

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

U2 - 10.1007/11601548_1

DO - 10.1007/11601548_1

M3 - Conference contribution

SN - 978-3-540-30911-6

VL - 3838

T3 - Lecture Notes in Computer Science

SP - 1

EP - 5

BT - Processes, Terms and Cycles: Steps on the Road to Infinity

A2 - Middeldorp, Aart

A2 - Oostrom, Vincent

A2 - Raamsdonk, Femke

A2 - Vrijer, Roel

PB - Springer Berlin Heidelberg

ER -

The Spectra of Words

Abstract

Publication series

Access to Document

Fingerprint

Cite this