电子学报 ›› 2021, Vol. 49 ›› Issue (12): 2479-2489.DOI: 10.12263/DZXB.20200404

• 综述评论 • 上一篇    下一篇

正则语言推断综述

高俊涛1, 王梅1, 徐光会1, 刘聪2   

  1. 1.东北石油大学计算机与信息技术学院,黑龙江 大庆 163318
    2.山东理工大学计算机科学与技术学院,山东 淄博 255000
  • 收稿日期:2020-04-27 修回日期:2021-01-06 出版日期:2021-12-25
    • 作者简介:
    • 高俊涛 男,1979年出生于黑龙江哈尔滨. 现为东北石油大学副教授、硕士生导师. 研究方向包括软件工程、过程建模、自动机学习等.E‑mail:gjt@nepu.edu.cn
      王 梅 女,1976年出生于河北安国.现为东北石油大学教授,研究方向包括机器学习、模型选择和核方法.E‑mail:wangmei@nepu.edu.cn
      徐光会 女,1995年出生于山东济宁.硕士研究生. 主要研究方向为自动机学习.E‑mail:xuguanghui6688@163.com
      刘 聪 男,1990年出生于山东淄博.现为山东理工大学教授,研究方向包括业务过程管理、过程挖掘、数据分析、Petri网理论与应用.E‑mail:liucongchina@sdust.edu.cn
    • 基金资助:
    • 国家自然科学基金 (51774090); 山东省泰山学者工程专项基金资助项目 (tsqn201909109); 大庆市指导性科技计划项目 (zd-2019-22)

A Survey on Regular Language Inference

GAO Jun-tao1, WANG Mei1, XU Guang-hui1, LIU Cong2   

  1. 1.School of Computer and Information Technology, Northeast Petroleum University, Daqing, Heilongjiang 163318, China
    2.School of Computer Science and Technology, Shandong University of Technology, Zibo, Shandong 255000, China
  • Received:2020-04-27 Revised:2021-01-06 Online:2021-12-25 Published:2021-12-25
    • Supported by:
    • National Natural Science Foundation of China (51774090); Program supported by Taishan Scholars Special Funding for Construction Projects of Shandong Province (tsqn201909109); Daqing Science and Technology Guide Plan of Heilongjiang Province (zd-2019-22)

摘要:

正则语言推断研究从语言的有限信息出发,通过归纳和推理得出正则语言模型.该技术在信息抽取、软件工程、模式识别等领域应用广泛.本文首先阐明了语言的可学习性概念和推断结果的评价准则.然后从推理策略、数据结构、算法复杂性等方面,对被动、主动和基于神经网络的学习算法进行分类归纳与对比,梳理各流派的技术发展脉络.接着分析推断产生的三种泛化效应.最后指出当前研究中不足,对未来研究方向进行展望.

关键词: 正则语言, 归纳学习, 正则推断, 自动机学习, 正则表达式学习, 循环神经网络

Abstract:

The regular language inference is devoted to the study of how to derive the definition of the language from the limited information. Regular language inference is popular in information extraction, software engineering, and schema learning, etc. The learnability models of regular languages and evaluation criteria are clarified. The passive, active, and neural network?based learning algorithms are respectively surveyed and compared from the aspects of reasoning strategies, data structures, algorithm complexity, etc, and the development trend is pointed out. Three kinds of generalization effects are analyzed. This paper points out the defects of the current researches and looks forward to future research directions.

Key words: regular languages, inductive inference, regular inference, automata learning, regular expression learning, recurrent neural network (RNN)

中图分类号: