Compact Representations of Search in Complex Domains

We consider the problem of searching in complex domains for a buggy element. The structure of the domain determines the set of possible queries at every stage of the search. An important type of search domain is a Directed Acyclic Graph (DAG), where one can query every sub-graph.

In this work we focus on reducing the number of sets required to represent a search domain. Our results include:

• An exact definition of general search domains as a set of sets.
• Modeling searching as a two player matrix game, in which a recursive representation allows us to apply backward induction to tackle the size representation problem.
• The set representation is powerful enough to represent almost any type of search; however, this generality usually requires exponential sizes. As it turns out, some specific types of search domains (like searching in DAGs) can be represented more compactly by using the original graph instead of sets. It is therefore important to determine which search domains (represented as sets) are actually isomorphic to a search in a DAG. We find necessary and sufficient conditions for representing search domains as DAGs, and show explicit constructions for transforming such search domains into DAGs.
  
  Search problems are often encountered in program testing or debugging. The bug should be found by searching the program's control graph using a minimal set of queries. Search problems also appear in the area of searching classified large tree-like data bases (e.g. the Yahoo's data base of the Internet).