A. Pelc, Lie patterns in search procedures,
Theoretical Computer Science 47 (1986), pp. 61-69.
A. Pelc, Lie patterns in search procedures,
Theoretical Computer Science 47 (1986), pp. 61-69.
Abstract:
We investigate the problem of identifying an unknown subset A of {1,...,n} using m queries of the form ``Does i belong to A?'' or, more generally, admitting all Boolean combination of such queries. The answers need not always be true but their sequence has to follow one of the lie patterns from a prescribed set H of binary sequences of length m (a 1 on the ith place forces the informing source to say the truth and a 0 to lie). We characterize those sets H for which the identification of A is possible and deal with the problem of the minimal size of H for which the set A can be hidden.
A. Pelc, Invariant ideals and Borel sets,
Proceedings of the American Mathematical Society 97 (1986), pp. 503-506.
Abstract:
We investigate the size of the algebra B(I), where B is the family of Borel sets and I is a translation invariant ideal of sets of reals. In particular the question whether B(I) can contain Vitali selectors or even all sets of reals is discussed in connection with the completeness of I and its invariance.
A. Pelc, Invariant measures and ideals on discrete groups,
Dissertationes Mathematicae 255 (1986), pp. 1-52.
Abstract:
In this dissertation we investigate the existence of invariant measures on large sigma-algebras on groups. We also consider the related problem of the existence of invariant extensions of such measures. A set theoretic notion tightly connected with the size of a measure is the saturation of an ideal. Hence we also study strongly saturated invariant ideals on groups.