{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T12:49:53Z","timestamp":1725454193376},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642341052"},{"type":"electronic","value":"9783642341069"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34106-9_12","type":"book-chapter","created":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T05:56:27Z","timestamp":1349070987000},"page":"111-123","source":"Crossref","is-referenced-by-count":2,"title":["On the Learnability of Shuffle Ideals"],"prefix":"10.1007","author":[{"given":"Dana","family":"Angluin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James","family":"Aspnes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aryeh","family":"Kontorovich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"39","key":"12_CR1","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0019-9958(78)90683-6","volume":"3","author":"D. Angluin","year":"1978","unstructured":"Angluin, D.: On the complexity of minimum inference of regular sets. Information and Control\u00a03(39), 337\u2013350 (1978)","journal-title":"Information and Control"},{"issue":"29","key":"12_CR2","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1145\/322326.322334","volume":"3","author":"D. Angluin","year":"1982","unstructured":"Angluin, D.: Inference of reversible languages. Journal of the ACM (JACM)\u00a03(29), 741\u2013765 (1982)","journal-title":"Journal of the ACM (JACM)"},{"issue":"2","key":"12_CR3","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D. Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput.\u00a075(2), 87\u2013106 (1987)","journal-title":"Inf. Comput."},{"issue":"1","key":"12_CR4","first-page":"7","volume":"14","author":"D. Angluin","year":"1994","unstructured":"Angluin, D., Slonim, D.K.: Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle. Machine Learning\u00a014(1), 7\u201326 (1994)","journal-title":"Machine Learning"},{"issue":"1","key":"12_CR5","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1023\/A:1007320031970","volume":"26","author":"N.H. Bshouty","year":"1997","unstructured":"Bshouty, N.H.: Exact learning of formulas in parallel. Machine Learning\u00a026(1), 25\u201341 (1997)","journal-title":"Machine Learning"},{"key":"12_CR6","first-page":"49","volume":"3","author":"N.H. Bshouty","year":"2002","unstructured":"Bshouty, N.H., Eiron, N.: Learning monotone DNF from a teacher that almost does not answer membership queries. Journal of Machine Learning Research\u00a03, 49\u201357 (2002)","journal-title":"Journal of Machine Learning Research"},{"issue":"4","key":"12_CR7","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1016\/j.jcss.2004.10.002","volume":"70","author":"N.H. Bshouty","year":"2005","unstructured":"Bshouty, N.H., Jackson, J.C., Tamon, C.: Exploring learnability between exact and PAC. J. Comput. Syst. Sci.\u00a070(4), 471\u2013484 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR8","first-page":"473","volume":"5","author":"A. Clark","year":"2004","unstructured":"Clark, A., Thollard, F.: Pac-learnability of probabilistic deterministic finite state automata. Journal of Machine Learning Research (JMLR)\u00a05, 473\u2013497 (2004)","journal-title":"Journal of Machine Learning Research (JMLR)"},{"key":"12_CR9","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/978-3-540-72927-3_26","volume-title":"Learning Theory","author":"C. Cortes","year":"2007","unstructured":"Cortes, C., Kontorovich, L.(A.), Mohri, M.: Learning Languages with Rational Kernels. In: Bshouty, N.H., Gentile, C. (eds.) COLT. LNCS (LNAI), vol.\u00a04539, pp. 349\u2013364. Springer, Heidelberg (2007)"},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"1332","DOI":"10.1016\/j.patcog.2005.01.003","volume":"38","author":"C. Higuera de la","year":"2005","unstructured":"de la Higuera, C.: A bibliographical study of grammatical inference. Pattern Recognition\u00a038, 1332\u20131348 (2005)","journal-title":"Pattern Recognition"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"55","DOI":"10.2307\/1969820","volume":"58","author":"S. Eilenberg","year":"1953","unstructured":"Eilenberg, S., Mac Lane, S.: On the groups of H(\u03a0,n). I. Ann. of Math. (2)\u00a058, 55\u2013106 (1953)","journal-title":"Ann. of Math. (2)"},{"issue":"37","key":"12_CR12","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"3","author":"E. Mark Gold","year":"1978","unstructured":"Mark Gold, E.: Complexity of automaton identification from given data. Information and Control\u00a03(37), 302\u2013420 (1978)","journal-title":"Information and Control"},{"issue":"2","key":"12_CR13","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0166-218X(96)00025-X","volume":"74","author":"Y. Ishigami","year":"1997","unstructured":"Ishigami, Y., Tani, S.: Vc-dimensions of finite automata and commutative finite automata with k letters and n states. Discrete Applied Mathematics\u00a074(2), 123\u2013134 (1997)","journal-title":"Discrete Applied Mathematics"},{"issue":"5","key":"12_CR14","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.dam.2010.08.022","volume":"159","author":"J.C. Jackson","year":"2011","unstructured":"Jackson, J.C., Lee, H.K., Servedio, R.A., Wan, A.: Learning random monotone DNF. Discrete Applied Mathematics\u00a0159(5), 259\u2013271 (2011)","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"12_CR15","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"M. Kearns","year":"1998","unstructured":"Kearns, M.: Efficient noise-tolerant learning from statistical queries. J. ACM\u00a045(6), 983\u20131006 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"12_CR16","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M.J. Kearns","year":"1994","unstructured":"Kearns, M.J., Valiant, L.G.: Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM)\u00a041(1), 67\u201395 (1994)","journal-title":"Journal of the ACM (JACM)"},{"key":"12_CR17","unstructured":"Kearns, M., Vazirani, U.: An Introduction to Computational Learning Theory. The MIT Press (1997)"},{"issue":"4","key":"12_CR18","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1142\/S0129054110007404","volume":"21","author":"O. Kl\u00edma","year":"2010","unstructured":"Kl\u00edma, O., Pol\u00e1k, L.: Hierarchies of piecewise testable languages. Int. J. Found. Comput. Sci.\u00a021(4), 517\u2013533 (2010)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"12_CR19","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/11894841_24","volume-title":"Algorithmic Learning Theory","author":"L. Kontorovich","year":"2006","unstructured":"Kontorovich, L.(A.), Cortes, C., Mohri, M.: Learning Linearly Separable Languages. In: Balc\u00e1zar, J.L., Long, P.M., Stephan, F. (eds.) ALT 2006. LNCS (LNAI), vol.\u00a04264, pp. 288\u2013303. Springer, Heidelberg (2006)"},{"issue":"3","key":"12_CR20","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.tcs.2008.06.037","volume":"405","author":"L. Kontorovich","year":"2008","unstructured":"Kontorovich, L.(A.), Cortes, C., Mohri, M.: Kernel methods for learning languages. Theor. Comput. Sci.\u00a0405(3), 223\u2013236 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR21","first-page":"997","volume":"10","author":"L. Kontorovich","year":"2009","unstructured":"Kontorovich, L.(A.), Nadler, B.: Universal Kernel-Based Learning with Applications to Regular Languages. Journal of Machine Learning Research\u00a010, 997\u20131031 (2009)","journal-title":"Journal of Machine Learning Research"},{"key":"12_CR22","unstructured":"Kontorovich, L.(A.), Ron, D., Singer, Y.: A Markov Model for the Acquisition of Morphological Structure. Technical Report CMU-CS-03-147 (2003)"},{"key":"12_CR23","unstructured":"Koskenniemi, K.: Two-level model for morphological analysis. In: IJCAI, pp. 683\u2013685 (1983)"},{"key":"12_CR24","unstructured":"Lothaire, M.: Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, vol.\u00a017. Addison-Wesley (1983)"},{"key":"12_CR25","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1017\/S135132499600126X","volume":"2","author":"M. Mohri","year":"1996","unstructured":"Mohri, M.: On some applications of finite-state automata theory to natural language processing. Nat. Lang. Eng.\u00a02, 61\u201380 (1996)","journal-title":"Nat. Lang. Eng."},{"issue":"2","key":"12_CR26","first-page":"269","volume":"23","author":"M. Mohri","year":"1997","unstructured":"Mohri, M.: Finite-state transducers in language and speech processing. Computational Linguistics\u00a023(2), 269\u2013311 (1997)","journal-title":"Computational Linguistics"},{"issue":"1","key":"12_CR27","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1109\/TASL.2009.2023170","volume":"18","author":"M. Mohri","year":"2010","unstructured":"Mohri, M., Moreno, P., Weinstein, E.: Efficient and robust music identification with weighted finite-state transducers. IEEE Transactions on Audio, Speech & Language Processing\u00a018(1), 197\u2013207 (2010)","journal-title":"IEEE Transactions on Audio, Speech & Language Processing"},{"issue":"1","key":"12_CR28","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/csla.2001.0184","volume":"16","author":"M. Mohri","year":"2002","unstructured":"Mohri, M., Pereira, F., Riley, M.: Weighted finite-state transducers in speech recognition. Computer Speech & Language\u00a016(1), 69\u201388 (2002)","journal-title":"Computer Speech & Language"},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"Oncina, J., Garc\u00eda, P.: Identifying regular languages in polynomial time. In: Advances in Structural and Syntactic Pattern Recognition, pp. 49\u201361. World Scientific Publishing (1992)","DOI":"10.1142\/9789812797919_0007"},{"issue":"1","key":"12_CR30","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.tcs.2007.07.023","volume":"387","author":"N. Palmer","year":"2007","unstructured":"Palmer, N., Goldberg, P.W.: PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance. Theor. Comput. Sci.\u00a0387(1), 18\u201331 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"1-2","key":"12_CR31","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1023\/A:1010822518073","volume":"44","author":"R. Parekh","year":"2001","unstructured":"Parekh, R., Honavar, V.G.: Learning DFA from simple examples. Mach. Learn.\u00a044(1-2), 9\u201335 (2001)","journal-title":"Mach. Learn."},{"key":"12_CR32","doi-asserted-by":"crossref","unstructured":"P\u0103un, G.: Mathematical Aspects of Natural and Formal Languages. World Scientific Publishing (1994)","DOI":"10.1142\/2497"},{"issue":"3","key":"12_CR33","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/0022-0000(90)90028-J","volume":"41","author":"L. Pitt","year":"1990","unstructured":"Pitt, L., Warmuth, M.: Prediction-preserving reducibility. Journal of Computer and System Sciences\u00a041(3), 430\u2013467 (1990)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"12_CR34","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1145\/138027.138042","volume":"40","author":"L. Pitt","year":"1993","unstructured":"Pitt, L., Warmuth, M.: The minimum consistent DFA problem cannot be approximated within any polynomial. Journal of the Association for Computing Machinery\u00a040(1), 95\u2013142 (1993)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"12_CR35","doi-asserted-by":"crossref","unstructured":"Rambow, O., Bangalore, S., Butt, T., Nasr, A., Sproat, R.: Creating a finite-state parser with application semantics. In: COLING (2002)","DOI":"10.3115\/1071884.1071910"},{"issue":"2","key":"12_CR36","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1006\/jcss.1997.1555","volume":"56","author":"D. Ron","year":"1998","unstructured":"Ron, D., Singer, Y., Tishby, N.: On the learnability and usage of acyclic probabilistic finite automata. Journal of Computer and System Sciences\u00a056(2), 133\u2013152 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR37","doi-asserted-by":"crossref","unstructured":"Sellie, L.: Learning random monotone DNF under the uniform distribution. In: COLT, pp. 181\u2013192 (2008)","DOI":"10.1145\/1536414.1536424"},{"issue":"1","key":"12_CR38","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.ic.2004.04.003","volume":"193","author":"R.A. Servedio","year":"2004","unstructured":"Servedio, R.A.: On learning monotone DNF under product distributions. Inf. Comput.\u00a0193(1), 57\u201374 (2004)","journal-title":"Inf. Comput."},{"key":"12_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1007\/3-540-07407-4_23","volume-title":"Automata Theory and Formal Languages","author":"I. Simon","year":"1975","unstructured":"Simon, I.: Piecewise Testable Events. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol.\u00a033, pp. 214\u2013222. Springer, Heidelberg (1975)"},{"issue":"3","key":"12_CR40","first-page":"377","volume":"22","author":"R. Sproat","year":"1996","unstructured":"Sproat, R., Shih, C., Gale, W., Chang, N.: A stochastic finite-state word-segmentation algorithm for Chinese. Computational Linguistics\u00a022(3), 377\u2013404 (1996)","journal-title":"Computational Linguistics"},{"issue":"11","key":"12_CR41","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Commun. ACM\u00a027(11), 1134\u20131142 (1984)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34106-9_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T00:53:51Z","timestamp":1687740831000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34106-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642341052","9783642341069"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34106-9_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}