I ett följedokument visades att den klass av konstant djupgående determinerade k-ary rekursiva klausuler är tillräckligt lärbar. I denna artikel presenterar vi negativa resultat som visar att varje naturlig generalisering av denna klass är svår att lära sig i Valiants modell av paclearnability. I synnerhet visar vi att följande program klasser är kryptografiskt svåra att lära: program med ett obegränsat antal konstant djup linjära rekursiva klausuler; program med en konstant djup determinera klausul som innehåller ett obegränsat antal rekursiva samtal; och program med en linjär rekursiv klausul av konstant lokalitet. Dessa resultat innebär omedelbart att någon mer allmän programklass inte är lärbar. Vi visar också att lära sig ett konstant fördjupat determinerat program med antingen två linjära rekursiva klausuler eller en linjär rekursiv klausul och en icke-rekursiv klausul är lika svårt som att lära boolean DNF. Tillsammans med positiva resultat från följedokumentet skapar dessa negativa resultat en gräns för eektiv inlärningsförmåga för rekursiva funktionsfria klausuler.
Som nämnts ovan, en följeslagare papper som presenterar negativa inlärningsförmåga resultat för flera naturliga generaliseringar av språket kd-MaxRecLang REF.
Pac-learning Recursive Logic Programs: Negative Results
{'venue': 'Journal of Artificial Intelligence Research, Vol 2, (1995), 541-573', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}