Revision #1 Authors: Yosi Ben-Asher, Eitan Farchi, Ilan Newman

Accepted on: 20th March 1997 00:00

Downloads: 1489

Keywords:

It is well known that the optimal solution for

searching in a finite total order set is binary search.

In binary search we divide the set into two ``halves'' by querying the middle

element and continue the search on the suitable half.

What is the equivalent of binary search when

the set $P$ is partially ordered?

A query in this case is to a point $x\in P$, with

two possible answers: 'yes', indicates that the required element

is ``below'' $x$, or 'no' if the element is not bellow $x$.

We show that the problem of computing an optimal strategy

for search in Posets that are tree-like (or forests) is

polynomial in the size of the tree, and requires at most $O(n^4\log^3 n)$ steps.

Optimal solutions of such search problems are often

needed in program testing and debugging,

where a given program is represented as a tree

and a bug should be found using a minimal set of queries.

This type of search is also applicable in searching

classified large tree-like data bases (e.g. the Internet).

TR96-044 Authors: Yosi Ben-Asher, Ilan Newman

Publication: 26th August 1996 12:05

Downloads: 1187

Keywords:

It is well known that the optimal solution for

searching in

a finite total order set is the binary search.

In the binary search we

divide the set into two ``halves'', by querying the middle

element, and continue the search on the suitable half.

What is the equivalent of binary search, when

the set $P$ is partially ordered?

A query in this case is to a point $x\in P$, with

two possible answers: 'yes', indicates that the required element

is ``below'' $x$, or 'no' if the element is not bellow $x$.

We show that the problem of computing an optimal strategy

for search in Posets that are tree-like (or forests) is

polynomial in the size of

the tree, and requires at most $O(n^2\log^2 n)$ steps.

Optimal solutions of such search problems are often

needed in program testing and debugging,

where a given program is represented as a tree

and a bug should be found using a minimal set of queries.