Finding a One-Variable Pattern from Incomplete Data Author: Hiroshi Sakamoto Source: Lecture Notes in Artificial Intelligence Vol. 1501, 1998, 234 - 246. Abstract. The present paper deals with the problem of finding a consistent one-variable pattern from incomplete positive and negative examples. The studied problems are called an extension E a consistent extension CE and a robust extension RE, respectively. Problem E corresponds to the ordinary problem to decide whether there exists a one-variable pattern that is consistent with the given positive and negative examples. As for the other problems, an example string is allowed to contain some unsettled symbols that can potentially match with every constant symbol. For the problem CE, one has to decide whether there exists a suitable assignment for these unsettled symbols as well as a one-variable pattern consistent with the examples with respect to the assignment chosen. Problem {\sc re} is the universal version of problem CE, i.e., now one has to decide whether there exists a one-variable pattern that is consistent with the examples under every assignment for the unsettled symbols. The decision problems defined are closely connected to the learnability of one-variable pattern languages from positive and negative examples. The computational complexity of the decision problems defined above is studied. In particular, it shown that RE is NP-complete. ©Copyright 1998 Springer