# Thue Symbol Sorting Theorem

Jump to navigation
Jump to 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