Decomposable Searching Problems.

Although searching is one of the most important problems in computer science and many particular results are known for searching problems, there really is no satisfactory, theory of searching. In this paper we propose a first step toward such a theory by defining the class of decomposable searching problems and them proving three theorems about problems in this class. These theorems are all of the form given a data structure D for a decomposable searching problem we can transform D into a new data structure D for a related problem. The correctness and complexity analysis of D are then used to establish the correctness and complexity of D. We present transforms for converting a static structure into a dynamic structure, for adding range variables to queries, and for making preprocessingquery time tradeoffs. These transforms have already been used to develop a number of best known theoretical algorithms, and promise to be an important tool in software engineering. Author