López Rodríguez, Damián, Calera Rubio, Jorge, Gallego, Antonio-Javier
Inference of k-testable directed acyclic graph languages
LÓPEZ, Damián; CALERA-RUBIO, Jorge; GALLEGO-SÁNCHEZ, Antonio-Javier. "Inference of k-testable directed acyclic graph languages". JMLR: Workshop and Conference Proceedings. Vol. 21 (2012). ISSN 1938-7288, pp. 149-163
URI: http://hdl.handle.net/10045/25780
DOI: 
ISSN: 1938-7288
Abstract: 
In this paper, we tackle the task of graph language learning. We first extend the well-known classes of k-testability and k-testability in the strict sense languages to directed graph languages. Second, we propose a graph automata model for directed acyclic graph languages. This graph automata model is used to 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.
Keywords:Graph languages, Graph automata, K-testable languages
JMLR
info:eu-repo/semantics/article