{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:15:04Z","timestamp":1737090904084,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540442394"},{"type":"electronic","value":"9783540457909"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45790-9_5","type":"book-chapter","created":{"date-parts":[[2007,5,16]],"date-time":"2007-05-16T02:46:02Z","timestamp":1179283562000},"page":"49-62","source":"Crossref","is-referenced-by-count":5,"title":["Consistent Identification in the Limit of Rigid Grammars from Strings Is NP-hard"],"prefix":"10.1007","author":[{"given":"Christophe Costa","family":"Flor\u00eancio","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,9,5]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Dana 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":"5_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0019-9958(80)90285-5","volume":"45","author":"D. Angluin","year":"1980","unstructured":"Dana Angluin. Inductive inference of formal languages from positive data. Information and Control, 45:117\u2013135, 1980.","journal-title":"Information and Control"},{"key":"5_CR3","unstructured":"Janis B\u0101rzdi\u0146\u0161. Inductive inference of automata, functions and programs. In Proceedings International Congress of Math., pages 455\u2013460, Vancouver, 1974."},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/BF00370157","volume":"49","author":"W. Buszkowski","year":"1990","unstructured":"Wojciech Buszkowski and Gerald Penn. Categorial grammars determined from linguistic data by unification. Studia Logica, 49:431\u2013454, 1990.","journal-title":"Studia Logica"},{"key":"5_CR5","unstructured":"Wojciech Buszkowski. Discovery procedures for categorial grammars. In E. Klein and J. van Benthem, editors, Categories, Polymorphism and Unification. University of Amsterdam, 1987."},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Christophe 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":"5_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/3-540-48199-0_8","volume-title":"LACL","author":"C. C. Flor\u00eancio","year":"2001","unstructured":"Christophe Costa Flor\u00eancio. Consistent Identification in the Limit of the Class k-valued is NP-hard. In Philippe de Groote, Glyn Morrill, and Christian Retor\u00e9, editors, LACL, volume 2099 of Lecture Notes in Computer Science, pages 125\u2013138. Springer, 2001."},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/S0019-9958(86)80042-0","volume":"69","author":"R. P. Daley","year":"1986","unstructured":"Robert P. Daley and Carl H. Smith. On the complexity of inductive inference. Information and Control, 69:12\u201340, 1986.","journal-title":"Information and Control"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(90)90042-G","volume":"85","author":"M. Fulk","year":"1990","unstructured":"Mark Fulk. Prudence and other conditions on formal language learning. Information and Computation, 85:1\u201311, 1990.","journal-title":"Information and Computation"},{"volume-title":"Computers and Intractability. A Guide to the Theory of NP-completeness","year":"1979","key":"5_CR10","unstructured":"Michael R. Garey and David S. Johnson, editors. Computers and Intractability. A Guide to the Theory of NP-completeness. Freeman, New York, 1979."},{"key":"5_CR11","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. Mark Gold. Language identification in the limit. Information and Control, 10:447\u2013474, 1967.","journal-title":"Information and Control"},{"key":"5_CR12","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":"5_CR13","unstructured":"Makoto Kanazawa. Learnable Classes of Categorial Grammars. CSLI Publications, Stanford University, 1998."},{"key":"5_CR14","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An Introduction to Computational Learning Theory","author":"M. J. Kearns","year":"1994","unstructured":"Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. Cambridge, Mass.: MIT Press, 1994."},{"key":"5_CR15","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":"5_CR16","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":"Leonard 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":"5_CR17","unstructured":"Richard P. Stanley. Excercises on Catalan and Related Numbers. http:\/\/www-math.mit.edu\/~rstan\/ec\/catalan.ps.gz , June 23rd 1998. Excerpted from [Sta99]."},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Richard P. Stanley. Enumerative Combinatorics, volume 2. Cambridge University Press, 1999.","DOI":"10.1017\/CBO9780511609589"},{"key":"5_CR19","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":"5_CR20","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1080\/09528139408953785","volume":"6","author":"R. Wiehagen","year":"1994","unstructured":"Rolf Wiehagen and Thomas Zeugmann. Ignoring data may be the only way to learn efficiently. Journal of Experimental and Theoretical Artificial Intelligence, 6:131\u2013144, 1994.","journal-title":"Journal of Experimental and Theoretical Artificial Intelligence"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"Rolf Wiehagen and Thomas 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"},{"key":"5_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1007\/3-540-60217-8_12","volume-title":"Algorithmic Learning for Knowledge-Based Systems-GOSLER Final Report","author":"T. Zeugmann","year":"1995","unstructured":"Thomas Zeugmann and Steffen Lange. A guided tour across the boundaries of learning recursive languages. In K. P. Jantke and S. Lange, editors, Algorithmic Learning for Knowledge-Based Systems-GOSLER Final Report, number 961 in Lecture Notes in Computer Science, pages 190\u2013258. Springer-Verlag, 1995."}],"container-title":["Lecture Notes in Computer Science","Grammatical Inference: Algorithms and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45790-9_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T09:18:31Z","timestamp":1737019111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45790-9_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540442394","9783540457909"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-45790-9_5","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}