Accession Number : AD0750539

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

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Habermann,Nico

Report Date : AUG 1972

Pagination or Media Count : 26

Abstract : The author of the Cigarette Smokers' Problem (S. Patil, MIT) tried to show that the problem could not be solved using Dijkstra's P- and V-operations without conditional statements. D. L. Parnas (CMU) showed that Patil's 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)

Descriptors :   (*OPERATIONS RESEARCH, PROBLEM SOLVING), COMPUTER PROGRAMMING, MATHEMATICAL MODELS, THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE