+ General Information
+ Members
+ Research
+ Intranet



15th workshop gRFIA

9th Music Encoding Conference (MEI 2021)


Alicante, July 19-23

13th international workshop on Machine Learning and Music


(online) September 18, 2020



  1. Gallego, A.J.; López, D.; Calera-Rubio, J.
    "Grammatical inference of directed acyclic graph languages with polynomial time complexity"
    Journal of Computer and System Sciences, vol. 95, pp. 19-34 (2018)
    : bibtex : URL

    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.

@article {
 author = "Gallego, A.J.; López, D.; Calera-Rubio, J.",
 title  = "Grammatical inference of directed acyclic graph languages with polynomial time complexity",
 issn = "0022-0000",
 journal = "Journal of Computer and System Sciences",
 pages = "19-34",
 volume = "95",
 year = "2018"
Resources associated with this publication
Valid XHTML 1.0!Valid CSS!