Accession Number:

AD0750539

Title:

On a Solution and a Generalization of the Cigarette Smokers' Problem,

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1972-08-01

Pagination or Media Count:

26.0

Abstract:

The author of the Cigarette Smokers Problem S. Patil, MIT tried to show that the problem could not be solved using Dijkstras P- and V-operations without conditional statements. D. L. Parnas CMU showed that Patils proof was false by presenting a solution using P- and V-operations, but no conditional statements. The paper presents first a correctness proof of Parnas solution. This solution leads to an obvious generalization and in connection with it the question of an optimal set of distinguishable codewords is addressed. Finally a more natural approach to the problem is discussed and a solution for this variation is presented with its correctness proof. Author

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE