{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T04:09:36Z","timestamp":1778299776106,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540584735","type":"print"},{"value":"9783540489856","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58473-0_134","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:17:01Z","timestamp":1330255021000},"page":"25-37","source":"Crossref","is-referenced-by-count":46,"title":["What is the search space of the regular inference?"],"prefix":"10.1007","author":[{"given":"P.","family":"Dupont","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L.","family":"Miclet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E.","family":"Vidal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"4_CR1","series-title":"Series in Automatic Computation","volume-title":"The Theory of Parsing, Translation and Compiling, Vol. 1: Parsing","author":"A. Aho","year":"1972","unstructured":"A. Aho and J. Ullman, The Theory of Parsing, Translation and Compiling, Vol. 1: Parsing, Series in Automatic Computation, Prentice-Hall, Englewood, Cliffs, 1972."},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0019-9958(78)90683-6","volume":"39","author":"D. Angluin","year":"1978","unstructured":"D. Angluin, On the Complexity of Minimum Inference of Regular Sets, Information and Control, Vol. 39, pp. 337\u2013350, 1978.","journal-title":"Information and Control"},{"issue":"No.3","key":"4_CR3","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1145\/322326.322334","volume":"29","author":"D. Angluin","year":"1982","unstructured":"D. Angluin, Inference of Reversible Languages, Journal of the ACM, Vol. 29, No. 3, pp. 741\u2013765, 1982.","journal-title":"Journal of the ACM"},{"key":"4_CR4","first-page":"85","volume":"5","author":"K.S. Fu","year":"1975","unstructured":"K.S. Fu and T.L. Booth, Grammatical Inference: Introduction and Survey, IEEE Transactions on SMC, Part 1: Vol. 5, pp. 85\u2013111, Part 2: Vol. 5, pp. 409\u2013423, 1975.","journal-title":"IEEE Transactions on SMC"},{"issue":"No.9","key":"4_CR5","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1109\/34.57687","volume":"12","author":"P. Garcia","year":"1990","unstructured":"P. Garcia and E. Vidal, Inference of K-testable languages in the strict sense and applications to syntactic pattern recognition, IEEE Transactions on PAMI, Vol. 12, No. 9, pp. 920\u2013925, 1990.","journal-title":"IEEE Transactions on PAMI"},{"issue":"No.1","key":"4_CR6","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1142\/S0218001494000140","volume":"8","author":"J. Gregor","year":"1994","unstructured":"J. Gregor, Data-driven Inductive Inference of Finite-state Automata, International Journal of Pattern Recognition and Artificial Intelligence, Vol. 8, No. 1, pp. 305\u2013322, 1994.","journal-title":"International Journal of Pattern Recognition and Artificial Intelligence"},{"issue":"No.5","key":"4_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, Vol. 10, No. 5, pp. 447\u2013474, 1967.","journal-title":"Information and Control"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E.M. Gold","year":"1978","unstructured":"E.M. Gold, Complexity of Automaton Identification from Given Data, Information and Control, Vol. 37, pp. 302\u2013320, 1978.","journal-title":"Information and Control"},{"key":"4_CR9","volume-title":"Introduction to Formal Language Theory","author":"M.A. Harrison","year":"1978","unstructured":"M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, Reading, Massachusetts, 1978."},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"M. Kearns and L. Valiant, Cryptographic Limitations on Learning Boolean Formulae and Finite Automata, Proc. of the 21st ACM Symposium on Theory of Computing, pp. 433\u2013444, 1989.","DOI":"10.1145\/73007.73049"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"K.J. Lang, Random DFA's can be Approximately Learned from Sparse Uniform Examples, Proc. of the 5th ACM workshop on Computational Learning Theory, pp. 45\u201352, 1992.","DOI":"10.1145\/130385.130390"},{"key":"4_CR12","volume-title":"Th\u00e8se de Docteur-Ing\u00e9nieur","author":"L. Miclet","year":"1979","unstructured":"L. Miclet, Inf\u00e9rence de Grammaires R\u00e9guli\u00e8res, Th\u00e8se de Docteur-Ing\u00e9nieur, E.N.S.T., Paris, France, 1979."},{"key":"4_CR13","first-page":"737","volume":"10","author":"L. Miclet","year":"1980","unstructured":"L. Miclet, Regular Inference with a Tail-Clustering Method, IEEE Trans. on SMC, Vol. 10, pp. 737\u2013743, 1980.","journal-title":"IEEE Trans. on SMC"},{"key":"4_CR14","unstructured":"L. Miclet and C. de Gentile, Inf\u00e9rence Grammaticale \u00e0 partir d'Exemples et de Contre-Exemples: deux Algorithmes Optimaux (BIG et RIG) et une Version Heuristique (BRIG), Actes des JFA-94, Strasbourg, France, pp. F1\u2013F13, 1994."},{"key":"4_CR15","unstructured":"S. Muggleton, Induction of Regular Languages from Positive Examples, Turing Institute Report, TIRM-84-009, 1984."},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"J. Oncina and P. Garcia, Inferring Regular Languages in Polynomial Update Time, Pattern Recognition and Image Analysis, N. Perrez de la Blanca, A. Sanfeliu and E. Vidal (editors), Series in Machine Perception and Artificial Intelligence, Vol. 1, pp. 49\u201361, World Scientific, 1992.","DOI":"10.1142\/9789812797902_0004"},{"key":"4_CR17","first-page":"18","volume-title":"Lecture Notes in Artificial Intelligence","author":"L. Pitt","year":"1989","unstructured":"L. Pitt, Inductive Inference, DFA's, and Computational Complexity, Lecture Notes in Artificial Intelligence, K.P. Jantke (editor), No. 397, Springer-Verlag, Berlin, pp. 18\u201344, 1989."},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"L. Pitt and M. Warmuth, The Minimum Consistent DFA Problem Cannot be Approximated Within any Polynomial, Tech. Report UIUCDCS-R-89-1499, University of Illinois, 1989.","DOI":"10.1145\/73007.73048"},{"key":"4_CR19","volume-title":"Finite Automata: Behavior and Synthesis","author":"B. Trakhtenbrot","year":"1973","unstructured":"B. Trakhtenbrot and Ya. Barzdin, Finite Automata: Behavior and Synthesis, North Holland Pub. Comp., Amsterdam, 1973."}],"container-title":["Lecture Notes in Computer Science","Grammatical Inference and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58473-0_134.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:21:52Z","timestamp":1605630112000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58473-0_134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540584735","9783540489856"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-58473-0_134","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]}}}