Resumen

Consideramos el problema del aprendizaje de máquinas de estados finitos no deterministas (NFSMs) a partir de sistemas en los que sus estructuras internas son implícitas y no deterministas. Recientemente, se ha propuesto un algoritmo para inferir NFSMs observables (ONFSMs), que son la subclase potencialmente aprendible de NFSMs, basado en la hipótesis de que se cumple el supuesto de prueba completa. Según este supuesto, con una secuencia de entrada (consulta), el conjunto completo de todas las posibles secuencias de salida viene dado por el llamado Maestro, de modo que el número de veces que se formula la misma consulta no se tiene en cuenta en el algoritmo. En este artículo, proponemos LNM*, un algoritmo de aprendizaje ONFSM refinado que considera la cantidad de veces que se repite la misma consulta como un parámetro. A diferencia de los trabajos anteriores, nuestro enfoque no requiere todas las secuencias de salida posibles en una respuesta. En su lugar, intenta observar las posibles secuencias de salida realizando la misma consulta muchas veces al Profesor. Hemos demostrado que LNM* puede inferir los ONFSM correspondientes de los sistemas desconocidos cuando el número de intentos para la misma consulta es adecuado para garantizar el supuesto de prueba completa. Además, la prueba demuestra que nuestro algoritmo terminará finalmente independientemente de que se cumpla o no la suposición. También presentamos el análisis teórico de la complejidad temporal de LNM*. Además, los resultados experimentales demuestran la eficacia práctica de nuestro enfoque.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:posibles secuencias de salida, misma consulta, suposición de prueba completa, algoritmo, lnm, máquinas de estados finitos no deterministas, análisis teórico de la complejidad temporal, nfsms, profesor, enfoque
• Keywords:possible output sequences, same query, complete testing assumption, algorithm, lnm, nondeterministic finite state machines, theoretical time complexity analysis, nfsms, teacher, approach