{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T09:40:12Z","timestamp":1737366012988,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422730"},{"type":"electronic","value":"9783540481997"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48199-0_8","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T08:25:15Z","timestamp":1186907115000},"page":"125-138","source":"Crossref","is-referenced-by-count":8,"title":["Consistent Identification in the Limit of Any of the Classes k-Valued Is NP-hard"],"prefix":"10.1007","author":[{"given":"Christophe Costa","family":"Flor\u00eancio","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,6,13]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"D. Angluin. Finding common patterns to a set of strings. In Proceedings of the 11th Annual Symposium on Theory of Computing, pages 130\u2013141, 1979.","DOI":"10.1145\/800135.804406"},{"key":"8_CR2","unstructured":"J. Barzdin. Inductive inference of automata, functions and programs. In Proceedings International Congress of Math., pages 455\u2013460, Vancouver, 1974."},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/BF00370157","volume":"49","author":"W. Buszkowski","year":"1990","unstructured":"W. Buszkowski and G. Penn. Categorial grammars determined from linguistic data by unification. Studia Logica, 49:431\u2013454, 1990.","journal-title":"Studia Logica"},{"key":"8_CR4","unstructured":"W. Buszkowski. Discovery procedures for categorial grammars. In E. Klein and J. van Benthem, editors, Categories, Polymorphism and Unification. University of Amsterdam, 1987."},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"C. Costa Flor\u00eancio. On the complexity of consistent identification of some classes of structure languages. In Arlindo L. Oliveira, editor, Grammatical Inference: Algorithms and Applications, volume 1891 of Lecture Notes in Artificial Intelligence, pages 89\u2013102. Springer-Verlag, 2000.","DOI":"10.1007\/978-3-540-45257-7_8"},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/S0019-9958(86)80042-0","volume":"69","author":"R. Daley","year":"1986","unstructured":"R. Daley and C. Smith. On the complexity of inductive inference. Information and Control, 69:12\u201340, 1986.","journal-title":"Information and Control"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"E. M. Gold","year":"1967","unstructured":"E. M. Gold. Language identification in the limit. Information and Control, 10:447\u2013474, 1967.","journal-title":"Information and Control"},{"key":"8_CR8","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6610.001.0001","volume-title":"Systems that Learn: An Introduction to Learning Theory","author":"S. Jain","year":"1999","unstructured":"Sanjay Jain, Daniel Osherson, James Royer, and Arun Sharma. Systems that Learn: An Introduction to Learning Theory. The MIT Press, Cambridge, MA., second edition, 1999.","edition":"second edition"},{"key":"8_CR9","unstructured":"M. Kanazawa. Learnable Classes of Categorial Grammars. CSLI Publications, Stanford University, 1998."},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF03037093","volume":"8","author":"S. Lange","year":"1991","unstructured":"Steffen Lange and Rolf Wiehagen. Polynomial time inference of arbitrary pattern languages. New Generation Computing, 8:361\u2013370, 1991.","journal-title":"New Generation Computing"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"D. N. Osherson, D. de Jongh, E. Martin, and S. Weinstein. Formal learning theory. In J. van Benthem and A. ter Meulen, editors, Handbook of Logic and Language. Elsevier Science Publishing, 1996.","DOI":"10.1016\/B978-044481714-3\/50017-5"},{"key":"8_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/3-540-51734-0_50","volume-title":"Proceedings of International Workshop on Analogical and Inductive Inference","author":"L. Pitt","year":"1989","unstructured":"L. Pitt. Inductive inference, dfas, and computational complexity. In K. P. Jantke, editor, Proceedings of International Workshop on Analogical and Inductive Inference, number 397 in Lecture Notes in Computer Science, pages 18\u201344, 1989."},{"key":"8_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/3-540-49730-7_30","volume-title":"Algorithmic Learning Theory (ALT)","author":"W. Stein","year":"1998","unstructured":"Werner Stein. Consistent polynominal identification in the limit. In Algorithmic Learning Theory (ALT), volume 1501 of Lecture Notes in Computer Science, pages 424\u2013438, Berlin, 1998. Springer-Verlag."},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"R. Wiehagen and T. Zeugmann. Learning and consistency. In K. P. Jantke and S. Lange, editors, Algorithmic Learning for Knowledge-Based Systems, number 961 in Lecture Notes in Artificial Intelligence, pages 1\u201324. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60217-8_1"}],"container-title":["Lecture Notes in Computer Science","Logical Aspects of Computational Linguistics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48199-0_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T08:58:10Z","timestamp":1737363490000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48199-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422730","9783540481997"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-48199-0_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}