{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:06:18Z","timestamp":1725663978391},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540573708"},{"type":"electronic","value":"9783540480969"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57370-4_58","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:55:51Z","timestamp":1330260951000},"page":"328-341","source":"Crossref","is-referenced-by-count":5,"title":["The VC-dimensions of finite automata with n states"],"prefix":"10.1007","author":[{"given":"Yoshiyasu","family":"Ishigami","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sei'ichi","family":"Tani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF03037090","volume":"8","author":"N. Abe","year":"1991","unstructured":"Abe, N.: Learning Commutative Deterministic Finite State Automata in Polynomial Time, New Generation Computing 8, 1991, pp.319\u2013335.","journal-title":"New Generation Computing"},{"key":"26_CR2","volume-title":"The Theory of Partitions","author":"G. Andrews","year":"1976","unstructured":"Andrews, G.: The Theory of Partitions, Addison-Wesley, Massachusetts (1976)."},{"key":"26_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, Information and Computation, Vol. 75, 1987, pp.87\u2013106.","journal-title":"Information and Computation"},{"key":"26_CR4","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D.: Queries and concept learning, Machine Learning, Vol. 2, 1988, pp.319\u2013342.","journal-title":"Machine Learning"},{"key":"26_CR5","first-page":"121","volume":"5","author":"D. Angluin","year":"1990","unstructured":"Angluin, D.: Negative results for equivalence queries, Machine Learning, Vol. 5, 1990, pp.121\u2013150.","journal-title":"Machine Learning"},{"key":"26_CR6","first-page":"444","volume":"ACM","author":"D. Angluin","year":"1991","unstructured":"Angluin, D. and M. Kharitonov: When Won't Membership Queries Help? in Proc. of 23nd STOC, ACM, 1991, pp.444\u2013454.","journal-title":"Proc. of 23nd STOC"},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Balcazar, J. L., J. Diaz, R. Gavalda and O. Watanabe: A Note on the Query Complexity of Learning DFA, Proc. of the 3rd workshop on Algorithmic Learning Theory, Japanese Society for AI, 1992, pp.53\u201362.","DOI":"10.1007\/3-540-57369-0_27"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Benedek, G. M. and A. Itai: Nonuniform learnability, International Colloquium on Automata, Languages and Programming 1988, Lecture Notes in Computer Science 317, Springer-Varlag, pp.82\u201392.","DOI":"10.1007\/3-540-19488-6_108"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Blumer, A., A. Ehrenfeucht, D. Haussler, and M. K. Warmuth: Classifying learnable geometric concepts with Vapnik-Chervonenkis dimension, in Proc. 18th ACM Symp. on Theory of Computing, 1986, pp.273\u2013282.","DOI":"10.1145\/12130.12158"},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0166-218X(89)90037-1","volume":"23","author":"J.-M. Champarnaud","year":"1989","unstructured":"Champarnaud, J.-M. and J.-E. Pin: A Maximin problem on finite automata, Discrete Applied Mathematics 23, 1989, pp.91\u201396.","journal-title":"Discrete Applied Mathematics"},{"key":"26_CR11","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"Hopcroft, J. E., and Ullman, J. D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Massachusetts (1979)."},{"key":"26_CR12","unstructured":"Ishigami, Y.: A Sperner set generating a k-dimensional Young tableaux, Preprint (1993)."},{"key":"26_CR13","unstructured":"Gaizer, T.: The Vapanik-Chervonenkis dimension of finite automata. Unpublished manuscript (1990)."},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"Maass, T., and G. Tur\u00e1n: On the complexity of learning from counterexamples, in Proc. 30th IEEE Symp. on Foundations of Computer Science 1989, pp.262\u2013167.","DOI":"10.1109\/SFCS.1989.63488"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Maass, T., and G. Tur\u00e1n: On the Complexity of Learning from Counterexamples and Membership Queries, in Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990, pp.203\u2013210.","DOI":"10.1109\/FSCS.1990.89539"},{"key":"26_CR16","volume-title":"Theory of Automata","author":"A. Salomaa","year":"1969","unstructured":"Salomaa, A.: Theory of Automata, Pergamon Press, Oxford, 1969."},{"key":"26_CR17","unstructured":"Watanabe, O.: A formal study of learnability via queries, International Colloquium on Automata, Languages and Programming, 1990, Lecture Notes in Computer Science 443, Springer-Varlag."},{"key":"26_CR18","unstructured":"Yokomori, T.: Learning Non-deterministic Finite Automata from Queries and Counterexamples. To appear in Machine Intelligence, Vol.13, Oxford Univ. Press."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57370-4_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:12:11Z","timestamp":1605647531000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57370-4_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540573708","9783540480969"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-57370-4_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}