caa a22 4500 445869585 CHVBK 20180317145507.0 cr unu---uuuuu 170323e20110201xx s 000 0 eng 10.1007/s00236-010-0130-7 doi (NATIONALLICENCE)springer-10.1007/s00236-010-0130-7 New bounds for the query complexity of an algorithm that learns DFAs with correction and equivalence queries [Elektronische Daten] [Victor Mitrana, Cristina Tîrnăucă] In this note, we show that the number of equivalence queries asked by an algorithm proposed in Becerra-Bonache etal. (Proceedings of the 8th International Colloquium on Grammatical Inference (ICGI '06), Lecture Notes in Artificial Intelligence, Springer-Verlag, Berlin 2006) that learns deterministic finite automata with correction and equivalence queries is at most the injectivity degree of the target language, a notion that corresponds to the number of repetitions among the correcting words of all the elements in the quotient of that language by the Myhill-Nerode equivalence. Further, we propose a tight upper bound for the number of correction queries as a function which depends on the index of the target language, the length of the longest counterexample returned by the teacher and the injectivity degree of the target language. However, the bounds obtained here for the number of CQs are optimal for the LCA algorithm, and they do not represent a tight upper bound for DFA learning with EQs and CQs in general. Springer-Verlag, 2010 Mitrana Victor Depto. Organización y Estructura de la Información, Universidad Politécnica de Madrid, Crta. de Valencia km. 7, 28031, Madrid, Spain aut Tîrnăucă Cristina Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria, Av. de los Castros s/n, 39005, Santander, Spain aut Acta Informatica Springer-Verlag 48/1(2011-02-01), 43-50 0001-5903 48:1<43 2011 48 236 https://doi.org/10.1007/s00236-010-0130-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00236-010-0130-7 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Mitrana Victor Depto. Organización y Estructura de la Información, Universidad Politécnica de Madrid, Crta. de Valencia km. 7, 28031, Madrid, Spain aut NATIONALLICENCE 700 1- Tîrnăucă Cristina Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria, Av. de los Castros s/n, 39005, Santander, Spain aut NATIONALLICENCE 773 0- Acta Informatica Springer-Verlag 48/1(2011-02-01), 43-50 0001-5903 48:1<43 2011 48 236 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer