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.