# Inference of k-Testable Directed Acyclic Graph Languages

[edit]

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.

#### Abstract

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