Polynomial-time learning of elementary formal systems

An elementary formal system (EFS) is a logic program consisting of definite clauses whose arguments have patterns instead of first-order terms. We inv estigate 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 i n the head. With this new notion, we show that H-EFS(m, k, t, r) is polynom ial-time learnable, which is the class of languages definable by EFSs consi sting of at most m hereditary definite clauses with predicate symbols of ar ity at most r, where Ic and t bound the number of variable occurrences in t he head and the number of atoms in the body, respectively. The class define d 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 E FSs. As hardness results, the class of regular pattern languages is shown n ot 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.