Grammatical inference of directed acyclic graph languages with polynomial time complexity

Empreu sempre aquest identificador per citar o enllaçar aquest ítem http://hdl.handle.net/10045/75210
Información del item - Informació de l'item - Item information
Títol: Grammatical inference of directed acyclic graph languages with polynomial time complexity
Autors: Gallego, Antonio-Javier | López Rodríguez, Damián | Calera Rubio, Jorge
Grups d'investigació o GITE: Reconocimiento de Formas e Inteligencia Artificial
Centre, Departament o Servei: Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos
Paraules clau: Graph languages | Graph automata | Grammatical inference | k-Testable languages
Àrees de coneixement: Lenguajes y Sistemas Informáticos
Data de publicació: d’agost-2018
Editor: Elsevier
Citació bibliogràfica: Journal of Computer and System Sciences. 2018, 95: 19-34. doi:10.1016/j.jcss.2017.12.002
Resum: 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
Tipus: info:eu-repo/semantics/article
Drets: © 2017 Elsevier Inc.
Revisió científica: si
Versió de l'editor: https://doi.org/10.1016/j.jcss.2017.12.002
Apareix a la col·lecció: INV - GRFIA - Artículos de Revistas

Arxius per aquest ítem:
Arxius per aquest ítem:
Arxiu Descripció Tamany Format  
Thumbnail2018_Gallego_etal_JCompSysSci_final.pdfVersión final (acceso restringido)807,26 kBAdobe PDFObrir     Sol·licitar una còpia
Thumbnail2018_Gallego_etal_JCompSysSci_accepted.pdfAccepted Manuscript (acceso abierto)860,69 kBAdobe PDFObrir Vista prèvia


Tots els documents dipositats a RUA estan protegits per drets d'autors. Alguns drets reservats.