Prefix-free regular-expression matching

Yo Sub Han; Yajun Wang; Derick Wood

doi:10.1007/11496656_26

Prefix-free regular-expression matching

Yo Sub Han, Yajun Wang, Derick Wood

College of Computing

Research output: Contribution to journal › Conference article › peer-review

7 Citations (Scopus)

Abstract

We explore the regular-expression matching problem with respect to prefix-freeness of the pattern. We show that the prefix-free regular expression gives only linear number of matching substrings in the size of a given text. Based on this observation, we propose an efficient algorithm for the prefix-free regular-expression matching problem. Furthermore, we suggest an algorithm to determine whether or not a given regular language is prefix-free.

Original language	English
Pages (from-to)	298-309
Number of pages	12
Journal	Lecture Notes in Computer Science
Volume	3537
DOIs	https://doi.org/10.1007/11496656_26
Publication status	Published - 2005
Event	Ot16th Annual Symposium on Combinatorial Pattern Matching, CPM 2005 - Jeju Island, Korea, Republic of Duration: 2005 Jun 19 → 2005 Jun 22

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/11496656_26

Cite this

@article{08ef6577f83e4d1fafa7145ad91884e9,

title = "Prefix-free regular-expression matching",

abstract = "We explore the regular-expression matching problem with respect to prefix-freeness of the pattern. We show that the prefix-free regular expression gives only linear number of matching substrings in the size of a given text. Based on this observation, we propose an efficient algorithm for the prefix-free regular-expression matching problem. Furthermore, we suggest an algorithm to determine whether or not a given regular language is prefix-free.",

author = "Han, {Yo Sub} and Yajun Wang and Derick Wood",

year = "2005",

doi = "10.1007/11496656_26",

language = "English",

volume = "3537",

pages = "298--309",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Verlag",

note = "Ot16th Annual Symposium on Combinatorial Pattern Matching, CPM 2005 ; Conference date: 19-06-2005 Through 22-06-2005",

}

TY - JOUR

T1 - Prefix-free regular-expression matching

AU - Han, Yo Sub

AU - Wang, Yajun

AU - Wood, Derick

PY - 2005

Y1 - 2005

N2 - We explore the regular-expression matching problem with respect to prefix-freeness of the pattern. We show that the prefix-free regular expression gives only linear number of matching substrings in the size of a given text. Based on this observation, we propose an efficient algorithm for the prefix-free regular-expression matching problem. Furthermore, we suggest an algorithm to determine whether or not a given regular language is prefix-free.

AB - We explore the regular-expression matching problem with respect to prefix-freeness of the pattern. We show that the prefix-free regular expression gives only linear number of matching substrings in the size of a given text. Based on this observation, we propose an efficient algorithm for the prefix-free regular-expression matching problem. Furthermore, we suggest an algorithm to determine whether or not a given regular language is prefix-free.

UR - http://www.scopus.com/inward/record.url?scp=26444504118&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26444504118&partnerID=8YFLogxK

U2 - 10.1007/11496656_26

DO - 10.1007/11496656_26

M3 - Conference article

AN - SCOPUS:26444504118

SN - 0302-9743

VL - 3537

SP - 298

EP - 309

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - Ot16th Annual Symposium on Combinatorial Pattern Matching, CPM 2005

Y2 - 19 June 2005 through 22 June 2005

ER -

Prefix-free regular-expression matching

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this