Presentation	2002/3/5 String Matching Algorithm for Extended Regular Expressions Ryuji ICHIKAWA, Hiroaki YAMAMOTO,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	In this paper, we are concerned with a string matching problem for extended regular expressions: Given an extended regular expression r of length m and a text string x of length n, determine if there exists a substring y of x such that y∈L(r), where L(r) denotes the language denoted by r. By using Yamamoto's recognition algorithm, we can simply solve this problem in O(mn^2 +kn^3) time and O(mn+kn^2) space. We implement this algorithm by using nondeterminisitic finite automata and deterministic finite automata, and evaluate the efficiency.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	extended regular expression / string matching algorithm
Paper #	COMP2001-98
Date of Issue

Conference Information
Committee	COMP
Conference Date	2002/3/5(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	String Matching Algorithm for Extended Regular Expressions
Sub Title (in English)
Keyword(1)	extended regular expression
Keyword(2)	string matching algorithm
1st Author's Name	Ryuji ICHIKAWA
1st Author's Affiliation	Graduate School of Science and Technology, Shinshu University()
2nd Author's Name	Hiroaki YAMAMOTO
2nd Author's Affiliation	Faculty of Engineering, Shinshu University
Date	2002/3/5
Paper #	COMP2001-98
Volume (vol)	vol.101
Number (no)	708
Page	pp.pp.-
#Pages	8
Date of Issue