Semi-membership algorithms
Derek E. Denny-Brown, Yenjo Han, Lane A. Hemaspaandra, Leen Torenvliet · ACM SIGACT News · 1994
A semi-membership algorithm for a set A is, informally, a program that when given any two strings determines which is logically more likely to be in A . A flurry of interest in this topic in the late seventies and early eighties was followed by a relatively quiescent half-decade. However, in the 1990s there has been a resurgence of interest in this topic. We survey recent work on the theory of semi-membership algorithms.