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.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v21-lopez12a, title = {Inference of $k$-Testable Directed Acyclic Graph Languages}, author = {Lòpez, Damiàn and Calera-Rubio, Jorge and Gallego-Sànchez, Javier}, booktitle = {Proceedings of the Eleventh International Conference on Grammatical Inference}, pages = {149--163}, year = {2012}, editor = {Heinz, Jeffrey and Higuera, Colin and Oates, Tim}, volume = {21}, series = {Proceedings of Machine Learning Research}, address = {University of Maryland, College Park, MD, USA}, month = {05--08 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v21/lopez12a/lopez12a.pdf}, url = {https://proceedings.mlr.press/v21/lopez12a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Inference of k-Testable Directed Acyclic Graph Languages %A Damiàn Lòpez %A Jorge Calera-Rubio %A Javier Gallego-Sànchez %B Proceedings of the Eleventh International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2012 %E Jeffrey Heinz %E Colin Higuera %E Tim Oates %F pmlr-v21-lopez12a %I PMLR %P 149--163 %U https://proceedings.mlr.press/v21/lopez12a.html %V 21 %X 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.
RIS
TY - CPAPER TI - Inference of k-Testable Directed Acyclic Graph Languages AU - Damiàn Lòpez AU - Jorge Calera-Rubio AU - Javier Gallego-Sànchez BT - Proceedings of the Eleventh International Conference on Grammatical Inference DA - 2012/08/16 ED - Jeffrey Heinz ED - Colin Higuera ED - Tim Oates ID - pmlr-v21-lopez12a PB - PMLR DP - Proceedings of Machine Learning Research VL - 21 SP - 149 EP - 163 L1 - http://proceedings.mlr.press/v21/lopez12a/lopez12a.pdf UR - https://proceedings.mlr.press/v21/lopez12a.html AB - 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. ER -
APA
Lòpez, D., Calera-Rubio, J. & Gallego-Sànchez, J.. (2012). Inference of k-Testable Directed Acyclic Graph Languages. Proceedings of the Eleventh International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 21:149-163 Available from https://proceedings.mlr.press/v21/lopez12a.html.

Related Material