Thue Symbol Sorting Theorem

Safalra's Special Thue Symbol Sorting Theorem (SSTSST) and Safalra's General Thue Symbol Sorting Theorem (SGTSST) place a lower bound on the speed of symbol sorting in Thue in terms of the number of string replacements made - namely that sorting is Omega(n^2), where n is the number of symbols to sort.

Terminology

• Bounded sorting - Sorting a number of items, each with bounded length
• Symbol sorting - Sorting a number of items, each of which is a single symbol
• Permutation symbol sorting - Sorting a number of items, each of which is a single symbol, using rules whose right-hand sides are permutations of their left-hand sides

Because a Thue program can only deal with a finite number of symbols, there are a finite number of possible items whose length is less than a fixed value. This means that bounded sorting can be converted into symbol sorting in Theta(n) time by converting each item into a single symbol.

The theorems

• Safalra's Special Thue Symbol Sorting Theorem - Permutation symbol sorting of n items runs in Omega(n^2) time
• Safalra's General Thue Symbol Sorting Theorem - Symbol sorting of n items runs in Omega(n^2) time

The proofs are complex and are not provided here.

External resources

• Sorting In Thue (dead link) - contains a proof of Safalra's Special Thue Symbol Sorting Theorem