Inference of k-Testable Directed Acyclic Graph Languages


Damián López, Jorge Calera-Rubio, Javier Gallego-Sánchez ;
Proceedings of the Eleventh International Conference on Grammatical Inference, PMLR 21:149-163, 2012.


In this paper, we tackle the task of graph language learning. We first extend the well-known classes of \emphk-testability and \emphk-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 \emphk-testable in the strict sense graph languages. The algorithm runs in polynomial time and identifies this class of languages from positive data.

Related Material