{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T20:01:22Z","timestamp":1794340882245,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540647768","type":"print"},{"value":"9783540687078","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054076","type":"book-chapter","created":{"date-parts":[[2006,7,6]],"date-time":"2006-07-06T10:54:16Z","timestamp":1152183256000},"page":"199-210","source":"Crossref","is-referenced-by-count":9,"title":["How considering incompatible state mergings may reduce the DFA induction search tree"],"prefix":"10.1007","author":[{"given":"Fran\u00e7ois","family":"Coste","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jacques","family":"Nicolas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2006,5,23]]},"reference":[{"key":"18_CR1","first-page":"291","volume-title":"Shape, Structure and Pattern Recognition","author":"R. Alqu\u00e9zar","year":"1995","unstructured":"R. Alqu\u00e9zar and A. Sanfeliu, \u201cIncremental grammatical inference from positive and negative data using unbiased finite state automata\u201d, In Shape, Structure and Pattern Recognition, Proc. Int. Workshop on Structural and Syntactic Pattern Recogni-tion, SSPR'94, Nahariya (Israel), World Scientific Pub., Singapore, 291\u2013300, 1995."},{"issue":"3","key":"18_CR2","first-page":"741","volume":"29","author":"D. Angluin","year":"1978","unstructured":"Angluin, D. On the complexity of minimum inference of regular sets. Information and Control 29(3):741\u2013765, 1978.","journal-title":"Information and Control"},{"key":"18_CR3","unstructured":"Coste, F. and Nicolas, J.: Regular Inference as a Graph Coloring Problem. Workshop on Grammar Inference, Automata Induction, and Language Acquisition (ICML' 97), Nashville, TN, 1997."},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Dupont, P. Regular Grammatical Inference from Positive and Negative Samples by Genetic Search: the GIG method. ICGI'94, Grammatical inference and Applications 236\u2013245. Springer Verlag, 1994.","DOI":"10.1007\/3-540-58473-0_152"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Dupont, P.; Miclet, L.; and E.Vidal. What is the search space of the regular inference ?ICGI'94, Grammatical inference and Applications 25\u201337. Springer Verlag, 1994.","DOI":"10.1007\/3-540-58473-0_134"},{"key":"18_CR6","unstructured":"Dupont, P. Utilisation et apprentissage de mod\u00e8les de langages pour la reconnaissance de la parole continue. Ph.D. Dissertation, Ecole Nationale Sup\u00e9rieure des T\u00e9l\u00e9communications, 1996."},{"key":"18_CR7","unstructured":"Giordano, J. Espace des versions et inf\u00e9rence de grammaires alg\u00e9briques. In Journ\u00e9es Francophones d'Apprentissage, 1993."},{"key":"18_CR8","unstructured":"Higuera (de la), C.; Oncina, J.; and Vidal, E.: Identification of DFA: data-dependent versus data-independent algorithms. Grammatical inference Learning Syntax from Sentences, ICGI'96 311\u2013325. Springer Verlag, 1996."},{"key":"18_CR9","unstructured":"Hirsh, H. Polynomial-time Learning with Version Spaces National Conference on Artificial Intelligence, San Jose, CA, 117\u2013122 july 1992."},{"key":"18_CR10","unstructured":"Juill\u00e9, H., and Pollack, J.B. SAGE: a Sampling-based Heuristic for Tree Search. Submitted paper."},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Kearns, M., and Valiant, L. Cryptographic limitation on learning boolean formulae and finite automata. In Proceedings of the Twenty First Annual Symposium on Theory of Computing, 433\u2013444, 1989.","DOI":"10.1145\/73007.73049"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"Lang, K. Random DFA's can be Approximately Learned from Sparse Uniform Examples. In proceedings of the fifth annual ACM Workshop on Computational Learning Theory 45\u201352, July 1992.","DOI":"10.1145\/130385.130390"},{"key":"18_CR13","unstructured":"Lang, K. Merge Order count NECI Tech Report, Sept26, 1997"},{"key":"18_CR14","unstructured":"Lang, K., and Pearlmutter, B., and Price, R. Results of the Abbadingo One DFA Learning Competition and a New Evidence Driven State Merging Algorithm. Submitted paper."},{"key":"18_CR15","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1142\/9789812814913_0009","volume-title":"Syntactic and Structural Pattern Recognition: Theory and Applications","author":"L. Miclet","year":"1990","unstructured":"Miclet, L. Grammatical Inference. Syntactic and Structural Pattern Recognition: Theory and Applications, Bunke, H. and Sanfeliu, A. Eds, Singapore, World Scientific,237\u2013290, 1990."},{"key":"18_CR16","unstructured":"Miclet, L., and de Gentille, C. Inf\u00e9rence grammaticale \u00e0 partir d'exemples et de contreexemples: deux algorithmes optimaux: (big et rig) et une version heuristique (brig). JAVA94, Journ\u00e9es Acquisition, Validation, Apprentissage F1\u2013F13, Strasbourg France, 1994."},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Mitchell, T. Generalization as search. Artificial Intelligence (18):203\u2013226, 1982.","DOI":"10.1016\/0004-3702(82)90040-6"},{"key":"18_CR18","unstructured":"Nicolas, J. Une repr\u00e9sentation efficace pour les espaces de versions. 8i\u00e8mes JFA, Saint-Raphael, 1993."},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"Oncina, J., and Garcia, P. Inferring regular languages in polynomial update time. Pattern Recognition and Image Analysis 49\u201361, 1993.","DOI":"10.1142\/9789812797902_0004"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Pao, T., and Carr, J. A solution for the syntactic induction inference problem for regular languages in Computer Language vol3 53\u201364, 1978.","DOI":"10.1016\/0096-0551(78)90006-1"},{"key":"18_CR21","unstructured":"Parekh, R., and Honavar, V. Efficient Learning of Regular Languages using Teacher Supplied Positive Examples and Learner Generated Queries. In Proceedings of the Fifth UNB Conference on AI, Fredrickton, Canada. 195\u2013203, August 1993."},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Quinlan, J.R. Induction of decision trees. Machine Learning (1):81\u2013106, 1986.","DOI":"10.1007\/BF00116251"},{"key":"18_CR23","unstructured":"Sebag, M. Une approche par contraintes de l'espace des versions. RFIA '94 17\u201325,1994."},{"key":"18_CR24","unstructured":"Trakhenbrot, B. and Barzdin, Y., Finite Automata: Behavior and Synthesis Amsterdam, North Holland Pub. Comp, 1973."},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"Vanlehn, K., and Ball, W. A version space approach to learning context-free grammars. Machine Learning (2):39\u201374, 1987.","DOI":"10.1007\/BF00058754"}],"container-title":["Lecture Notes in Computer Science","Grammatical Inference"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054076","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,19]],"date-time":"2019-04-19T17:21:50Z","timestamp":1555694510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0054076"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540647768","9783540687078"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/bfb0054076","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/bfb0054058","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}