Prefix-free regular-expression matching

Yo Sub Han, Yajun Wang, Derick Wood

Research output: Contribution to journalConference articlepeer-review

7 Citations (Scopus)


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 languageEnglish
Pages (from-to)298-309
Number of pages12
JournalLecture Notes in Computer Science
Publication statusPublished - 2005
EventOt16th Annual Symposium on Combinatorial Pattern Matching, CPM 2005 - Jeju Island, Korea, Republic of
Duration: 2005 Jun 192005 Jun 22

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Prefix-free regular-expression matching'. Together they form a unique fingerprint.

Cite this