| Article ID: | iaor19911585 |
| Country: | Netherlands |
| Volume: | 30 |
| Issue: | 2/3 |
| Start Page Number: | 265 |
| End Page Number: | 273 |
| Publication Date: | Feb 1991 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Wagner Dorothea, Wagner Frank |
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 stages 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.