RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación
Artículo científico (JournalArticle)
Inference of k-Testable Directed Acyclic Graph Languages
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., Damián López is partially supported by the Spanish Ministerio de Economía y Competitividad under research project TIN2011-28260-C03-01. Jorge Calera-Rubio and Antonio-Javier Gallego-Sánchez thank the Spanish CICyT for partial support of this work through project TIN2009-14205-C04-01, the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778, and the program CONSOLIDER INGENIO2010 (CSD2007-00018).