The Setting
Shortest common superstring is an optimization problem on finite words. Its objective uses a symbol count, while running time uses the bit length of the explicitly represented input.
List Delimiters
Write for an empty sequence and for concatenation, and represent bits by and . For a map taking elements to bit strings, write for a list with first element and remaining list ; the prefix marker list encoding is the bit string defined recursively by (1): (1)✦
The Definition
Definition 1. An ordinary symbol is a finite bit string, with symbol alphabet given by (2): (2)✦ A word over the alphabet is a finite sequence of symbols from ; the set of words is (3): (3)✦ An instance is a finite list of words, belonging to the instance set in (4): (4)✦
The symbol encoding is the function from ordinary symbols to bit strings that applies the list encoding (1) with the one-bit encoding , as specified in (5): (5)✦ The word encoding is the function from words to bit strings that encodes each word’s list of symbols according to (6): (6)✦ For an instance , its instance encoding is the bit string in (7): (7)✦ Write for the symbol length of a word, for the total input symbol length, and for the encoded input bit length.
A common superstring of an instance is a word containing every input word as a contiguous substring, as in (8); empty factors are permitted: (8)✦ The unrestricted optimum is the minimum symbol length of a common superstring among all words in , as in (9): (9)✦
A function has a polynomial-time implementation if a deterministic stack machine with a finite alphabet for each stack computes in time polynomial in .✦ Here denotes these machines: (10)✦
What Is Checked
The definitions are stated over the words and instances in (3) and (4), and over deterministic stack machines with a finite alphabet for each stack in (10).