Unions of a Bounded Number of Tree Pattern Languages Are Hard To Learn
Hiroki Arimura, 博紀 有村 · QIR (Kyushu University Institutional Repository) (Kyushu University) · 1994
In this paper, we show that for every positive integer k, the class $ \\tau \\rho iota^k $ of unions of at most k tree pattern languages is not learnable unless P = NP in the framework of PAC-learnability.