TY - GEN

T1 - Polynomial-time learning of elementary formal systems

AU - Miyano, Satoru

AU - Shinohara, Ayumi

AU - Shinohara, Takeshi

PY - 2000

Y1 - 2000

N2 - An elementary formal system (EFS) is a logic program consisting of definite clauses whose arguments have patterns instead of first-order terms. We investigate EFSs for polynomial-time PAC-learnability. A definite clause of an EFS is hereditary if every pattern in the body is a subword of a pattern in the head. With this new notion, we show that H-EFS(m, k, t, r) is polynomial-time learnable, which is the class of languages definable by EFSs consisting of at most m hereditary definite clauses with predicate symbols of arity at most r, where k and t bound the number of variable occurrences in the head and the number of atoms in the body, respectively. The class defined by all finite unions of EFSs in H-EFS(m, k, t, r) is also polynomial-time learnable. We also show an interesting series of NC-learnable classes of EFSs. As hardness results, the class of regular pattern languages is shown not polynomial-time learnable unless RP = NP. Furthermore, the related problem of deciding whether there is a common subsequence which is consistent with given positive and negative examples is shown NP-complete.

AB - An elementary formal system (EFS) is a logic program consisting of definite clauses whose arguments have patterns instead of first-order terms. We investigate EFSs for polynomial-time PAC-learnability. A definite clause of an EFS is hereditary if every pattern in the body is a subword of a pattern in the head. With this new notion, we show that H-EFS(m, k, t, r) is polynomial-time learnable, which is the class of languages definable by EFSs consisting of at most m hereditary definite clauses with predicate symbols of arity at most r, where k and t bound the number of variable occurrences in the head and the number of atoms in the body, respectively. The class defined by all finite unions of EFSs in H-EFS(m, k, t, r) is also polynomial-time learnable. We also show an interesting series of NC-learnable classes of EFSs. As hardness results, the class of regular pattern languages is shown not polynomial-time learnable unless RP = NP. Furthermore, the related problem of deciding whether there is a common subsequence which is consistent with given positive and negative examples is shown NP-complete.

UR - http://www.scopus.com/inward/record.url?scp=0033726227&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033726227&partnerID=8YFLogxK

U2 - 10.1007/BF03037530

DO - 10.1007/BF03037530

M3 - Article

AN - SCOPUS:0033726227

SN - 0288-3635

VL - 18

SP - 217

EP - 242

JO - New Generation Computing

JF - New Generation Computing

ER -