Grammatical inference of directed acyclic graph languages with polynomial time complexity
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/75210
Título: | Grammatical inference of directed acyclic graph languages with polynomial time complexity |
---|---|
Autor/es: | Gallego, Antonio-Javier | López Rodríguez, Damián | Calera Rubio, Jorge |
Grupo/s de investigación o GITE: | Reconocimiento de Formas e Inteligencia Artificial |
Centro, Departamento o Servicio: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos |
Palabras clave: | Graph languages | Graph automata | Grammatical inference | k-Testable languages |
Área/s de conocimiento: | Lenguajes y Sistemas Informáticos |
Fecha de publicación: | ago-2018 |
Editor: | Elsevier |
Cita bibliográfica: | Journal of Computer and System Sciences. 2018, 95: 19-34. doi:10.1016/j.jcss.2017.12.002 |
Resumen: | In this paper we study the learning of graph languages. We extend the well-known classes of k-testability and k-testability in the strict sense languages to directed graph languages. We propose a grammatical inference algorithm to learn the class of directed acyclic k-testable in the strict sense graph languages. The algorithm runs in polynomial time and identifies this class of languages from positive data. We study its efficiency under several criteria, and perform a comprehensive experimentation with four datasets to show the validity of the method. Many fields, from pattern recognition to data compression, can take advantage of these results. |
URI: | http://hdl.handle.net/10045/75210 |
ISSN: | 0022-0000 (Print) | 1090-2724 (Online) |
DOI: | 10.1016/j.jcss.2017.12.002 |
Idioma: | eng |
Tipo: | info:eu-repo/semantics/article |
Derechos: | © 2017 Elsevier Inc. |
Revisión científica: | si |
Versión del editor: | https://doi.org/10.1016/j.jcss.2017.12.002 |
Aparece en las colecciones: | INV - GRFIA - Artículos de Revistas |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
2018_Gallego_etal_JCompSysSci_final.pdf | Versión final (acceso restringido) | 807,26 kB | Adobe PDF | Abrir Solicitar una copia |
2018_Gallego_etal_JCompSysSci_accepted.pdf | Accepted Manuscript (acceso abierto) | 860,69 kB | Adobe PDF | Abrir Vista previa |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.