On the complexity of learning strings and sequences
作者： Ming Li , Tao Jiang
关键词:
摘要: It is shown that strings (sequences) cannot be learned by (sequences, resp.) in Valiant's distribution tree (pac) learning model, assuming RP ≠ NP.
acm.org
sci-hub.st 参考文章(7)
Esko Ukkonen, Jorma Tarhio, Hannu Peltola, Hans Söderlund, Algorithms for Some String Matching Problems Arising in Molecular Genetics. ifip congress. pp. 59- 64 ,(1983)
R. Board, L. Pitt, On the necessity of Occam algorithms symposium on the theory of computing. pp. 54- 63 ,(1990) , 10.1145/100216.100223
L. G. Valiant, A theory of the learnable symposium on the theory of computing. ,vol. 27, pp. 1134- 1142 ,(1984) , 10.1145/800057.808710
John Gallant, David Maier, James Astorer, On finding minimal length superstrings Journal of Computer and System Sciences. ,vol. 20, pp. 50- 58 ,(1980) , 10.1016/0022-0000(80)90004-5
David Maier, The Complexity of Some Problems on Subsequences and Supersequences Journal of the ACM. ,vol. 25, pp. 322- 336 ,(1978) , 10.1145/322063.322075
Alfred V. Aho, Margaret J. Corasick, Efficient string matching: an aid to bibliographic search Communications of The ACM. ,vol. 18, pp. 333- 340 ,(1975) , 10.1145/360825.360855
Leonard Pitt, Leslie G. Valiant, Computational limitations on learning from examples Journal of the ACM. ,vol. 35, pp. 965- 984 ,(1988) , 10.1145/48014.63140