{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T04:25:14Z","timestamp":1744259114262,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642341052"},{"type":"electronic","value":"9783642341069"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34106-9_10","type":"book-chapter","created":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T05:56:27Z","timestamp":1349070987000},"page":"81-95","source":"Crossref","is-referenced-by-count":2,"title":["Regular Inference as Vertex Coloring"],"prefix":"10.1007","author":[{"given":"Christophe","family":"Costa Flor\u00eancio","sequence":"first","affiliation":[]},{"given":"Sicco","family":"Verwer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-540-30195-0_4","volume-title":"Grammatical Inference: Algorithms and Applications","author":"J. Abela","year":"2004","unstructured":"Abela, J., Coste, F., Spina, S.: Mutually Compatible and Incompatible Merges for the Search of the Smallest Consistent DFA. In: Paliouras, G., Sakakibara, Y. (eds.) ICGI 2004. LNCS (LNAI), vol.\u00a03264, pp. 28\u201339. Springer, Heidelberg (2004)"},{"key":"10_CR2","unstructured":"Akram, H.I., Batard, A., de la Higuera, C., Eckert, C.: PSMA: A parallel algorithm for learning regular languages. In: NIPS Workshop on Learning on Cores, Clusters and Clouds (2010)"},{"issue":"3","key":"10_CR3","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0019-9958(78)90683-6","volume":"39","author":"D. Angluin","year":"1978","unstructured":"Angluin, D.: On the complexity of minimum inference of regular sets. Information and Control\u00a039(3), 337\u2013350 (1978)","journal-title":"Information and Control"},{"issue":"2","key":"10_CR4","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.jalgor.2004.06.008","volume":"54","author":"R. Beigel","year":"2005","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time O(1.3289 n ). Journal of Algorithms\u00a054(2), 168\u2013204 (2005)","journal-title":"Journal of Algorithms"},{"key":"10_CR5","unstructured":"Biere, A., Heule, M.J.H., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol.\u00a0185. IOS Press (February 2009)"},{"issue":"6","key":"10_CR6","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1109\/TC.1972.5009015","volume":"21","author":"A.W. Biermann","year":"1972","unstructured":"Biermann, A.W., Feldman, J.A.: On the synthesis of finite-state machines from samples of their behavior. IEEE Trans. Comput.\u00a021(6), 592\u2013597 (1972)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"10_CR7","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A. Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput.\u00a039(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"key":"10_CR8","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\u00a038, 1457\u20131467 (2005)","journal-title":"Pattern Recognition"},{"issue":"6","key":"10_CR9","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/j.orl.2004.03.002","volume":"32","author":"J.M. Byskov","year":"2004","unstructured":"Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters\u00a032(6), 547\u2013556 (2004)","journal-title":"Operations Research Letters"},{"key":"10_CR10","unstructured":"Coste, F., Nicolas, J.: Regular inference as a graph coloring problem. In: Workshop on Grammatical Inf., Automata Ind., and Language Acq., ICML 1997 (1997)"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"de la Higuera, C.: Grammatical Inference: Learning Automata and Grammars. Cambridge University Press (2010)","DOI":"10.1017\/CBO9781139194655"},{"key":"10_CR12","series-title":"LNAI","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/978-3-642-15488-1_6","volume-title":"Grammatical Inference: Theoretical Results and Applications","author":"P. Garc\u00eda","year":"2010","unstructured":"Garc\u00eda, P., V\u00e1zquez de Parga, M., L\u00f3pez, D., Ruiz, J.: Learning Automata Teams. In: Sempere, J.M., Garc\u00eda, P. (eds.) ICGI 2010. LNCS (LNAI), vol.\u00a06339, pp. 52\u201365. Springer, Heidelberg (2010)"},{"key":"10_CR13","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. (1979)"},{"issue":"3","key":"10_CR14","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E.M. Gold","year":"1978","unstructured":"Gold, E.M.: Complexity of automaton identification from given data. Information and Control\u00a037(3), 302\u2013320 (1978)","journal-title":"Information and Control"},{"key":"10_CR15","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/11814771_40","volume-title":"Automated Reasoning","author":"O. Grinchtein","year":"2006","unstructured":"Grinchtein, O., Leucker, M., Piterman, N.: Inferring Network Invariants Automatically. In: Furbach, U., Shankar, N. (eds.) IJCAR 2006. LNCS (LNAI), vol.\u00a04130, pp. 483\u2013497. Springer, Heidelberg (2006)"},{"key":"10_CR16","series-title":"LNAI","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":"M.J.H. 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 (LNAI), vol.\u00a06339, pp. 66\u201379. Springer, Heidelberg (2010)"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D. Karger","year":"1998","unstructured":"Karger, D., Motwani, R., Sudan, M.: Approximate graph coloring by semidefinite programming. J. ACM\u00a045, 246\u2013265 (1998)","journal-title":"J. ACM"},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M.J. Kearns","year":"1994","unstructured":"Kearns, M.J., Valiant, L.: Cryptographic limitations on learning Boolean formulae and finite automata. J. ACM\u00a041, 67\u201395 (1994)","journal-title":"J. ACM"},{"key":"10_CR19","unstructured":"Lang, K.J.: Faster algorithms for finding minimal consistent DFAs. Technical report, NEC Research Institute (1999)"},{"key":"10_CR20","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0054059","volume-title":"Grammatical Inference","author":"K.J. 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.\u00a01433, pp. 1\u201312. Springer, Heidelberg (1998)"},{"issue":"1","key":"10_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.1475-3995.2009.00696.x","volume":"17","author":"E. Malaguti","year":"2010","unstructured":"Malaguti, E., Toth, P.: A survey on vertex coloring problems. International Transactions in Operational Research\u00a017(1), 1\u201334 (2010)","journal-title":"International Transactions in Operational Research"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Oliveira, A.L., Marques-Silva, J.P.: Efficient search techniques for the inference of minimum sized finite state machines. In: String Processing and Information Retrieval, pp. 81\u201389 (1998)","DOI":"10.1109\/SPIRE.1998.712986"},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Oncina, J., Garcia, P.: Inferring regular languages in polynomial update time. In: Pattern Recognition and Image Analysis. Series in Machine Perception and Artificial Intelligence, vol.\u00a01, pp. 49\u201361. World Scientific (1992)","DOI":"10.1142\/9789812797902_0004"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Pitt, L., Warmuth, M.K.: The minimum consistent DFA problem cannot be approximated within any polynomial. In: STOC, pp. 421\u2013432 (1989)","DOI":"10.1145\/73007.73048"},{"key":"10_CR25","unstructured":"Sudkamp, T.A.: Languages and Machines: an introduction to the theory of computer science, 3rd edn. Addison-Wesley (2006)"},{"key":"10_CR26","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, 1\u201334 (to appear)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34106-9_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T20:50:49Z","timestamp":1744231849000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34106-9_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642341052","9783642341069"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34106-9_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}