## Finding a One-Variable Pattern from Incomplete Data
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 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 |