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 \emph{$k$-testability} and \emph{$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.

Related Material