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).

By: Yosi Ben-Asher, Eitan Farchi

Published in: H-0212 in 2003


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .