Algorithms for learning regular expressions from positive data

被引：47
作者：
Fernau, Henning [1 ]
机构：
[1] Univ Trier, FB 4, Abt Informat, D-54286 Trier, Germany
来源：
INFORMATION AND COMPUTATION | 2009年 / 207卷 / 04期
关键词：
Regular expressions; Identification in the limit from positive data; Text learning; LANGUAGE; IDENTIFICATION; INFERENCE; GRAMMARS;
D O I：
10.1016/j.ic.2008.12.008
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We describe algorithms that directly infer very simple forms of 1-unambiguous regular expressions from positive data. Thus, we characterize the regular language classes that can be learned this way, both in terms of regular expressions and in terms of (not necessarily minimal) deterministic finite automata. (C) 2009 Elsevier Inc. All rights reserved.
引用
收藏
页码：521 / 541
页数：21
相关论文
共 55 条
[1]  
Ahonen H, 1997, LECT NOTES COMPUT SC, V1293, P27
[2]  
AHONEN H, 1994, LECT NOTES ARTIF INT, V862, P153
[3]   INFERENCE OF REVERSIBLE LANGUAGES [J].
ANGLUIN, D .
JOURNAL OF THE ACM, 1982, 29 (03) :741-765
[4]  
ANHANG E, EXTENSIBLE MARKUP LA
[5]   Formal properties of XML grammars and languages [J].
Berstel, J ;
Boasson, L .
ACTA INFORMATICA, 2002, 38 (09) :649-671
[6]  
Bertoni A, 2006, LECT NOTES COMPUT SC, V4036, P108
[7]  
Bex G. J., 2006, VLDB, P115
[8]  
Blackwell AlanF., 2001, YOUR WISH IS MY COMM, P245
[9]  
BLATTNER M, 1976, THEORY COMPUTING SYS, V10, P253
[10]   GENERALIZED REGULAR EXPRESSIONS - A LANGUAGE FOR SYNTHESIS OF PROGRAMS WITH BRANCHING IN LOOPS [J].
BRAZMA, A ;
KINBER, E .
THEORETICAL COMPUTER SCIENCE, 1986, 46 (2-3) :175-195
123456