The combination of non-determinism and sorting is mostly associated with permutation sort, a sorting algorithm that is not very useful for sorting and has an awful running time.
In this paper we look at the combination of non-determinism and sorting in a different light: given a sorting function, we apply it to a non-deterministic predicate to gain a function that enumerates permutations of the input list. We get to the bottom of necessary properties of the sorting algorithms and predicates in play as well as discuss variations of the modelled non-determinism.
On top of that, we formulate and prove a theorem stating that no matter which sorting function we use, the corresponding permutation
function enumerates all permutations of the input list. We use free theorems, which are derived from the type of a function
alone, to prove the statement.
Mon 19 Sep
|17:00 - 17:25|
Kotaro TakedaUniversity of Tokyo, Japan, Naoki KobayashiUniversity of Tokyo, Japan, Kazuya YaguchiTohoku University, Japan, Ayumi ShinoharaTohoku University, JapanDOI
|17:25 - 17:50|
Shin-Cheng MuAcademia Sinica, Taiwan, Yu-Hsi ChiangNational Taiwan University, Taiwan, Yu-Han LyuDartmouth College, USADOI
|17:50 - 18:15|
Jan ChristiansenFlensburg University of Applied Sciences, Germany, Nikita DanilenkoUniversity of Kiel, Germany, Sandra DylusUniversity of Kiel, GermanyDOI