Inference of k-testable directed acyclic graph languages
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10045/25780
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). |
URI: | http://hdl.handle.net/10045/25780 |
ISSN: | 1938-7288 |
Language: | eng |
Type: | info:eu-repo/semantics/article |
Peer Review: | si |
Publisher version: | http://jmlr.csail.mit.edu/proceedings/papers/v21/ |
Appears in Collections: | INV - GRFIA - Artículos de Revistas |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
lopez12a.pdf | 183,22 kB | Adobe PDF | Open Preview | |
Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.