Grammatical inference of directed acyclic graph languages with polynomial time complexity

作者：

Highlights：

• We tackle the task of graph language learning.

• We extend the classes of k-testability and k-TSS languages to directed graph languages.

• We propose a grammatical inference algorithm to learn this class of languages.

• The algorithm runs in polynomial time.

• The algorithm identifies this class of languages from positive data.

摘要

•We tackle the task of graph language learning.•We extend the classes of k-testability and k-TSS languages to directed graph languages.•We propose a grammatical inference algorithm to learn this class of languages.•The algorithm runs in polynomial time.•The algorithm identifies this class of languages from positive data.

论文关键词：Graph languages,Graph automata,Grammatical inference,k-Testable languages

论文评审过程：Received 15 July 2016, Revised 25 September 2017, Accepted 14 December 2017, Available online 29 December 2017, Version of Record 30 April 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.12.002