From regular weighted expressions to finite automata

被引：0

作者：

Champarnaud, JM ^{[1
]}

Laugerotte, É ^{[1
]}

Ouardi, F ^{[1
]}

Ziadi, D ^{[1
]}

机构：

[1] Univ Rouen, LIFAR, Rouen, France

来源：

IMPLEMENTATION AND APPLICATION OF AUTOMATA, PROCEEDINGS | 2003年 / 2759卷

关键词：

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In this article we generalize the concepts of position automaton and ZPC structure to the regular K-expressions. We show that the ZPC structure can be built in linear time in the size of the expression and that the associated position automaton can be deduced from it in quadratic time.

引用

页码：49 / 60

页数：12

共 13 条

[1] Partial derivatives of regular expressions and finite automaton constructions
Antimirov, V
[J]. THEORETICAL COMPUTER SCIENCE, 1996, 155 (02) : 291 - 319
[2] Berstel J., 1988, RATIONAL SERIES THEI
[3] Caron P, 2001, LECT NOTES COMPUT SC, V2088, P67
[4] Champarnaud J.-M., 2001, Combinatorial Pattern Matching. 12th Annual Symposium, CPM 2001. Proceedings (Lecture Notes in Computer Science Vol. 2089), P157
[5] Subset construction complexity for homogeneous automata, position automata and ZPC-structures
Champarnaud, JM
[J]. THEORETICAL COMPUTER SCIENCE, 2001, 267 (1-2) : 17 - 34
[6] Glushkov V M, 1961, Russian Mathematical Survey, V16, P1, DOI DOI 10.1070/RM1961V016N05ABEH004112
[7] Hebisch U., 1993, Semirings Algebraic Theory and Applications in Computer Science
[8] Kuich W., 1986, SEMIRINGS AUTOMATA L, DOI [10.1007/978-3-642-69959-7, DOI 10.1007/978-3-642-69959-7]
[9] LOMBARDY S, 2001, 2001D001 ENST
[10] McNaughton R., 1960, IEEE TRANS ELECTRON, V9, P39, DOI [10.1109/TEC.1960.5221603, DOI 10.1109/TEC.1960.5221603]

← 1 2 →