Inference of k-testable directed acyclic graph languages

Please use this identifier to cite or link to this item:
Información del item - Informació de l'item - Item information
Title: Inference of k-testable directed acyclic graph languages
Authors: López Rodríguez, Damián | Calera Rubio, Jorge | Gallego, Antonio-Javier
Research Group/s: Reconocimiento de Formas e Inteligencia Artificial
Center, Department or Service: Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos | Universidad Politécnica de Valencia. Departamento de Sistemas Informáticos y Computación
Keywords: Graph languages | Graph automata | K-testable languages
Knowledge Area: Lenguajes y Sistemas Informáticos
Issue Date: 2012
Publisher: JMLR
Citation: 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
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.
Sponsor: 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 INGENIO 2010 (CSD2007-00018).
ISSN: 1938-7288
Language: eng
Type: info:eu-repo/semantics/article
Peer Review: si
Publisher version:
Appears in Collections:INV - GRFIA - Artículos de Revistas

Files in This Item:
Files in This Item:
File Description SizeFormat 
Thumbnaillopez12a.pdf183,22 kBAdobe PDFOpen Preview

Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.