Technical Report 217-1989
- Title
- A Generalization of the Zero-One Principle for Sorting Algorithms
- Authors
- Dorothea Wagner and Frank Wagner
- Publication
- DISAM, vol. 30, 1991, pp. 265-273
- Source
-
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
- Classification
-
not available
- Keywords
-
not available
-
In this paper a new general approach for the so-called "zero-one principle" for sorting algorithms is described. A theorem from propositional logic that states the connection between two-valued logic and many-valued logic is used to prove this zero-one principle. As a consequence a zero-one principle for a more general class of sorting algorithms is derived.