Can I read Sets Represented as the Length-n Factors of a Word on EtoBox?

Sets Represented as the Length-n Factors of a Word by Tan, Shuo; Shallit, Jeffrey is a scholarly article available to read on EtoBox.

What is Sets Represented as the Length-n Factors of a Word about?

In this paper we consider the following problems: how many different subsets of Sigma^n can occur as set of all length-n factors of a finite word? If a subset is representable, how long a word do we need to represent it? How many such subsets are represented by words of length t? For the first problem, we give upper and lower bounds of the form alpha^(2^n) in the binary case. For the second problem, we give a weak upper bound and some experimental data. For the third problem, we give a closed-form formula in the case where n <= t < 2n. Algorithmic variants of these problems have previously been studied under the name "shortest common superstring".

Author

Tan, Shuo; Shallit, Jeffrey

Published

2013

Language

EN