A common superstring of a finite family of finite words is a word containing every member of as a contiguous substring. Write for the minimum length of such a word, measured in symbols. The input words are represented explicitly, including their encoded symbol labels and boundaries. Let be the total bit length of this representation. The shortest common superstring problem asks for a common superstring of minimum symbol length.
Tarhio and Ukkonen conjectured that the greedy maximum-overlap procedure attains factor . Blum, Jiang, Li, Tromp and Yannakakis gave the first polynomial-time constant-factor guarantee, , and later guarantees include by Sweedyk, by Mucha, by Englert, Matsakis and Veselý, and by Chukhin, Kulikov, Mihajlin and Smal.
The preprint proves that a deterministic algorithm, running in time polynomial in , returns a common superstring of symbol length at most for every finite input family.
The Lean library Superstring treats ordinary strings whose symbols are bit strings. Its main theorem gives an algorithm such that, for every finite input family , is a common superstring of length at most , and can be computed in time polynomial in by a machine over a finite alphabet.
The results on these pages are those of the Lean library, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every one of them, so the Lean library is the reference: where the preprint states a result differently, the statement on the page is the Lean library’s, and the preprint’s is given beside it. The preprint gives the results their order and their names.
Superstring is a Lean library: 23 items, in seven groups. Each has a page written by OctoInform, listed below.
No item matches.