- -

Grammatical inference of directed acyclic graph languages with polynomial time complexity

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

Grammatical inference of directed acyclic graph languages with polynomial time complexity

Show simple item record

Files in this item

dc.contributor.author Gallego, Antonio-Javier es_ES
dc.contributor.author López Rodríguez, Damián es_ES
dc.contributor.author Calera-Rubio, Jorge es_ES
dc.date.accessioned 2020-02-13T21:00:54Z
dc.date.available 2020-02-13T21:00:54Z
dc.date.issued 2018 es_ES
dc.identifier.issn 0022-0000 es_ES
dc.identifier.uri http://hdl.handle.net/10251/136876
dc.description.abstract [EN] 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. es_ES
dc.language Inglés es_ES
dc.publisher Elsevier es_ES
dc.relation.ispartof Journal of Computer and System Sciences es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Graph languages es_ES
dc.subject Graph automata es_ES
dc.subject Grammatical inference es_ES
dc.subject K-Testable languages es_ES
dc.subject.classification LENGUAJES Y SISTEMAS INFORMATICOS es_ES
dc.title Grammatical inference of directed acyclic graph languages with polynomial time complexity es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1016/j.jcss.2017.12.002 es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation Gallego, A.; López Rodríguez, D.; Calera-Rubio, J. (2018). Grammatical inference of directed acyclic graph languages with polynomial time complexity. Journal of Computer and System Sciences. 95:19-34. https://doi.org/10.1016/j.jcss.2017.12.002 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1016/j.jcss.2017.12.002 es_ES
dc.description.upvformatpinicio 19 es_ES
dc.description.upvformatpfin 34 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 95 es_ES
dc.relation.pasarela S\361559 es_ES


This item appears in the following Collection(s)

Show simple item record