Grammatical inference of directed acyclic graph languages with polynomial time complexity

Please use this identifier to cite or link to this item:
Información del item - Informació de l'item - Item information
Title: Grammatical inference of directed acyclic graph languages with polynomial time complexity
Authors: Gallego, Antonio-Javier | López Rodríguez, Damián | Calera Rubio, Jorge
Research Group/s: Reconocimiento de Formas e Inteligencia Artificial
Center, Department or Service: Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos
Keywords: Graph languages | Graph automata | Grammatical inference | k-Testable languages
Knowledge Area: Lenguajes y Sistemas Informáticos
Issue Date: Aug-2018
Publisher: Elsevier
Citation: Journal of Computer and System Sciences. 2018, 95: 19-34. doi:10.1016/j.jcss.2017.12.002
Abstract: 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.
ISSN: 0022-0000 (Print) | 1090-2724 (Online)
DOI: 10.1016/j.jcss.2017.12.002
Language: eng
Type: info:eu-repo/semantics/article
Rights: © 2017 Elsevier Inc.
Peer Review: si
Publisher version:
Appears in Collections:INV - GRFIA - Artículos de Revistas

Files in This Item:
Files in This Item:
File Description SizeFormat 
Thumbnail2018_Gallego_etal_JCompSysSci_final.pdfVersión final (acceso restringido)807,26 kBAdobe PDFOpen    Request a copy
Thumbnail2018_Gallego_etal_JCompSysSci_accepted.pdfAccepted Manuscript (acceso abierto)860,69 kBAdobe PDFOpen Preview

Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.