Comment on 

Volume 11, article R8 (January 5, 2004)

"Strings with maximally many distinct subsequences and substrings"

Abraham Flaxman, Aram W. Harrow and Gregory B. Sorkin


Comment by the authors, January 19, 2004:

Just a week after publication of our article, Prof. Jan Snellman of Stockholm University brought to our attention an important reference we overlooked, a 1993 article [Sha93] by Prof. Jeffrey O. Shallit of the University of Waterloo.  Our Theorem 8 (for the substring problem) should now be thought of as generalizing Shallit's Theorems 1 and 2 from alphabet size d=2 to arbitrary d, with the added observation that for d > 2 the maximizing strings can be taken as prefixes of a single infinite string, while for d=2 this is not possible.

We regret our oversight, perhaps arising from a failure to search on "factors" or "subwords" as well as "substrings", and we thank Prof. Shallit for his understanding.

Prof. Snellman also pointed out a technical error.  In the statement of Theorem 8 (as is already correctly elucidated in its proof), k should not be the integer part of logd(n) but rather the integer such that dk+k-1 ≤ n < dk+1+(k+1)-1.

We are very grateful to Prof. Snellman for pointing out the two errors, and pleased that the electronic format of E-JC allows us to redress them promptly.

Readers may also be interested in a recent paper by Svante Janson, Stefano Lonardi, and Wojciech Szpankowski [JLS03] and additional references cited therein.


Also, the authors have made subsequent further comments.

References

[JLS03] Svante Janson, Stefano Lonardi, and Wojciech Szpankowski, On the average sequence complexity, Tech. Report 2003:41, Uppsala Univ., November 2003.

[Sha93] Jeffrey Shallit, On the maximum number of distinct factors in a binary string, Graphs Combin. 9 (1993), no. 2, 197-200. MR94b:05015