Grammatical inference of directed acyclic graph languages with polynomial time complexity

被引：2

作者：

Gallego, Antonio-Javier ^{[1
]}

Lopez, Damian ^{[2
]}

Calera-Rubio, Jorge ^{[1
]}

机构：

[1] Univ Alicante, Dept Software & Comp Syst, Pattern Recognit & Artificial Intelligence Grp, Alicante 03690, Spain

[2] Univ Politecn Valencia, Dept Sistemas Informat & Computac, E-46022 Valencia, Spain

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2018年 / 95卷

关键词：

Graph languages; Graph automata; Grammatical inference; k-Testable languages; CONTEXT-FREE GRAMMARS; TESTABLE TREE-LANGUAGES; IDENTIFICATION; RECOGNITION; AUTOMATA; INFORMATION; PREDICTION; LIMIT;

D O I：

10.1016/j.jcss.2017.12.002

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we study the learning of graph languages. We extend the well-known classes of k-testability and k-testability in the strict sense languages to directed graph languages. We 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. We study its efficiency under several criteria, and perform a comprehensive experimentation with four datasets to show the validity of the method. Many fields, from pattern recognition to data compression, can take advantage of these results. (C) 2017 Elsevier Inc. All rights reserved.

引用

页码：19 / 34

页数：16

共 36 条

[21] Noisy Time Series Prediction using Recurrent Neural Networks and Grammatical Inference
C. Lee Giles
Steve Lawrence
Ah Chung Tsoi
Machine Learning, 2001, 44 : 161 - 183
[22] Noisy time series prediction using recurrent neural networks and grammatical inference
Giles, CL
Lawrence, S
Tsoi, AC
MACHINE LEARNING, 2001, 44 (1-2) : 161 - 183
[23] Polynomial time PAC learnability of a sub-class of linear languages
Tajima, Y
Kotani, Y
Terada, M
PDPTA '04: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS 1-3, 2004, : 338 - 344
[24] A Classification Approach Based on Directed Acyclic Graph to Predict Locomotion Activities With One Inertial Sensor on the Thigh
Papapicco, V
Chen, B.
Munih, M.
Davalli, A.
Sacchetti, R.
Gruppioni, E.
Crea, S.
Vitiello, N.
IEEE TRANSACTIONS ON MEDICAL ROBOTICS AND BIONICS, 2021, 3 (02): : 436 - 445
[25] On the capacity of generalized write-once memory with state transitions described by an arbitrary directed acyclic graph
Fu, FW
Vinck, AJH
IEEE TRANSACTIONS ON INFORMATION THEORY, 1999, 45 (01) : 308 - 313
[26] Polynomial time learning of simple deterministic languages via queries and a representative sample
Tajima, Y
Tomita, E
Wakatsuki, M
Terada, M
THEORETICAL COMPUTER SCIENCE, 2004, 329 (1-3) : 203 - 221
[27] Using Adaptive Directed Acyclic Graph for Human In-Hand Motion Identification with Hybrid Surface Electromyography and Kinect
Xue, Yaxu
Yu, Yadong
Yin, Kaiyang
Du, Haojie
Li, Pengfei
Dai, Kejie
Ju, Zhaojie
SYMMETRY-BASEL, 2022, 14 (10):
[28] SAR-Oriented Visual Saliency Model and Directed Acyclic Graph Support Vector Metric Based Target Classification
Amrani, Moussa
Jiang, Feng
Xu, Yunzhong
Liu, Shaohui
Zhang, Shengping
IEEE JOURNAL OF SELECTED TOPICS IN APPLIED EARTH OBSERVATIONS AND REMOTE SENSING, 2018, 11 (10) : 3794 - 3810
[29] A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
Mescoff, Guillaume
Paul, Christophe
Thilikos, Dimitrios M.
DISCRETE APPLIED MATHEMATICS, 2022, 312 : 72 - 85
[30] Urban Land Cover Mapping by Spatial-Spectral Feature Analysis of High Resolution Hyperspectral Data with Decision Directed Acyclic Graph SVM
Huang, Y. Cheng
Li, Pingxiang
Zhang, Liangpei
Zhong, Y.
2009 JOINT URBAN REMOTE SENSING EVENT, VOLS 1-3, 2009, : 614 - 620

← 1 2 3 4 →