Searching for quicksand ideals in partially ordered sets

Abstract: We consider a combinatorial question about searching for an unknown ideal

m u

within a known poset

l a m b d a

. Elements of

l a m b d a

may be queried for membership in

m u

, but at most

k

positive query results are permitted. The goal is to find a search strategy which guarantees a solution in a minimal total number

m_{k} (l a m b d a)

of queries. We provide tight bounds for

m_{k} (l a m b d a)

, and construct optimal search strategies for the case where

k = 2

and

l a m b d a

is the product poset of totally ordered finite sets, one of which has cardinality not more than six.

Recommendations

Cites work

Cited in

(2)

Describes a project that uses

Uses Software

This page was built for publication: Searching for quicksand ideals in partially ordered sets