Thue Symbol Sorting Theorem

From Esolang
Jump to: navigation, search

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 - contains a proof of Safalra's Special Thue Symbol Sorting Theorem