{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:25Z","timestamp":1759637605704,"version":"3.40.5"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319155784"},{"type":"electronic","value":"9783319155791"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-15579-1_48","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T08:36:13Z","timestamp":1424680573000},"page":"611-622","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["BFS-Based Symmetry Breaking Predicates for DFA Identification"],"prefix":"10.1007","author":[{"given":"Vladimir","family":"Ulyantsev","sequence":"first","affiliation":[]},{"given":"Ilya","family":"Zakirzyanov","sequence":"additional","affiliation":[]},{"given":"Anatoly","family":"Shalyto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"48_CR1","unstructured":"Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (2006)"},{"issue":"9","key":"48_CR2","doi-asserted-by":"publisher","first-page":"1332","DOI":"10.1016\/j.patcog.2005.01.003","volume":"38","author":"C De La Higuera","year":"2005","unstructured":"De La Higuera, C.: A bibliographical study of grammatical inference. Pattern Recognition 38(9), 1332\u20131348 (2005)","journal-title":"Pattern Recognition"},{"issue":"3","key":"48_CR3","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"EM Gold","year":"1978","unstructured":"Gold, E.M.: Complexity of automaton identification from given data. Information and Control 37(3), 302\u2013320 (1978)","journal-title":"Information and Control"},{"issue":"1","key":"48_CR4","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1145\/138027.138042","volume":"40","author":"L Pitt","year":"1993","unstructured":"Pitt, L., Warmuth, M.K.: The minimum consistent DFA problem cannot be approximated within any polynomial. Journal of the ACM 40(1), 95\u2013142 (1993)","journal-title":"Journal of the ACM"},{"key":"48_CR5","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0054059","volume-title":"Grammatical Inference","author":"KJ Lang","year":"1998","unstructured":"Lang, K.J., Pearlmutter, B.A., Price, R.A.: Results of the abbadingo one DFA learning competition and a new evidence-driven state merging algorithm. In: Honavar, V.G., Slutzki, G. (eds.) ICGI 1998. LNCS (LNAI), vol. 1433, pp. 1\u2013112. Springer, Heidelberg (1998)"},{"key":"48_CR6","unstructured":"Lang, K.J.: Faster Algorithms for Finding Minimal Consistent DFAs. Technical report (1999)"},{"issue":"9","key":"48_CR7","doi-asserted-by":"publisher","first-page":"1457","DOI":"10.1016\/j.patcog.2004.03.027","volume":"38","author":"M Bugalho","year":"2005","unstructured":"Bugalho, M., Oliveira, A.L.: Inference of regular languages using state merging algorithms with search. Pattern Recognition 38(9), 1457\u20131467 (2005)","journal-title":"Pattern Recognition"},{"key":"48_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/3-540-58473-0_152","volume-title":"Grammatical Inference and Applications","author":"P Dupont","year":"1994","unstructured":"Dupont, P.: Regular grammatical inference from positive and negative samples by genetic search: the GIG method. In: Carrasco, R.C., Oncina, J. (eds.) ICGI 1994. LNCS, vol. 862, pp. 236\u20132445. Springer, Heidelberg (1994)"},{"key":"48_CR9","unstructured":"Luke, S., Hamahashi, S., Kitano, H.: Genetic programming. In: Proceedings of the Genetic and Evolutionary Computation Conference, vol. 2, pp. 1098\u20131105 (1999)"},{"key":"48_CR10","doi-asserted-by":"crossref","unstructured":"Lucas, S.M., Reynolds, T.J.: Learning DFA: evolution versus evidence driven state merging. In: The 2003 Congress on Evolutionary Computation, CEC 2003, vol. 1, pp. 351\u2013358. IEEE (2003)","DOI":"10.1109\/CEC.2003.1299597"},{"key":"48_CR11","unstructured":"Lucas, S.: GECCO 2004 noisy DFA results. In: GECCO Proc. (2004)"},{"issue":"7","key":"48_CR12","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1109\/TPAMI.2005.143","volume":"27","author":"SM Lucas","year":"2005","unstructured":"Lucas, S.M., Reynolds, T.J.: Learning deterministic finite automata with a smart state labeling evolutionary algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence 27(7), 1063\u20131074 (2005)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"48_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-642-15488-1_7","volume-title":"Grammatical Inference: Theoretical Results and Applications","author":"MJH Heule","year":"2010","unstructured":"Heule, M.J.H., Verwer, S.: Exact DFA identification using SAT solvers. In: Sempere, J.M., Garc\u00eda, P. (eds.) ICGI 2010. LNCS, vol. 6339, pp. 66\u201379. Springer, Heidelberg (2010)"},{"issue":"4","key":"48_CR14","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1007\/s10664-012-9210-3","volume":"18","author":"N Walkinshaw","year":"2013","unstructured":"Walkinshaw, N., Lambeau, B., Damas, C., Bogdanov, K., Dupont, P.: STAMINA: a competition to encourage the development and assessment of software model inference techniques. Empirical Software Engineering 18(4), 791\u2013824 (2013)","journal-title":"Empirical Software Engineering"},{"key":"48_CR15","unstructured":"Biere, A., Heule, M., van Maaren, H.: Handbook of satisfiability, vol. 185. IOS Press (2009)"},{"key":"48_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/11560548_20","volume-title":"Correct Hardware Design and Verification Methods","author":"N Amla","year":"2005","unstructured":"Amla, N., Du, X., Kuehlmann, A., Kurshan, R.P., McMillan, K.L.: An analysis of SAT-based model checking techniques in an industrial environment. In: Borrione, D., Paul, W. (eds.) CHARME 2005. LNCS, vol. 3725, pp. 254\u2013268. Springer, Heidelberg (2005)"},{"key":"48_CR17","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1007\/978-3-540-69052-8_70","volume-title":"New Frontiers in Applied Artificial Intelligence","author":"R Lohfert","year":"2008","unstructured":"Lohfert, R., Lu, J.J., Zhao, D.: Solving SQL constraints by incremental translation to SAT. In: Nguyen, N.T., Borzemski, L., Grzech, A., Ali, M. (eds.) IEA\/AIE 2008. LNCS (LNAI), vol. 5027, pp. 669\u2013676. Springer, Heidelberg (2008)"},{"key":"48_CR18","doi-asserted-by":"crossref","unstructured":"Galeotti, J.P., Rosner, N., Lopez Pombo, C.G., Frias, M.F.: TACO: Efficient SAT-Based Bounded Verification Using Symmetry Breaking and Tight Bounds. IEEE Transactions on Software Engineering 39(9), 1283\u20131307 (2013)","DOI":"10.1109\/TSE.2013.15"},{"key":"48_CR19","doi-asserted-by":"crossref","unstructured":"Ulyantsev, V., Tsarev, F.: Extended finite-state machine induction using SAT-solver. In: Proc. of ICMLA 2011, vol. 2, pp. 346\u2013349. IEEE (2011)","DOI":"10.1109\/ICMLA.2011.166"},{"key":"48_CR20","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-540-88009-7_11","volume-title":"Grammatical Inference: Algorithms and Applications","author":"B Lambeau","year":"2008","unstructured":"Lambeau, B., Damas, C., Dupont, P.E.: State-merging DFA induction algorithms with mandatory merge constraints. In: Clark, A., Coste, F., Miclet, L. (eds.) ICGI 2008. LNCS (LNAI), vol. 5278, pp. 139\u2013153. Springer, Heidelberg (2008)"},{"key":"48_CR21","unstructured":"Chambers, L.D.: Practical handbook of genetic algorithms: complex coding systems, vol. 3. CRC Press (2010)"},{"key":"48_CR22","unstructured":"Barahona, P., H\u00f6lldobler, S., Nguyen, V.: Efficient SAT-encoding of linear csp constraints. In: 13th International Symposium on Artificial Intelligence and Mathematics-ISAIM, Fort Lauderdale, Florida, USA (2014)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15579-1_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T21:57:20Z","timestamp":1747691840000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-15579-1_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319155784","9783319155791"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15579-1_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 February 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}