Prefix-free regular languages and pattern matching

We explore the regular-expression matching problem with respect to prefix-freeness of the pattern. We prove that a prefix-free regular expression gives only a linear number of matching substrings in the size of a given text. Based on this observation, we propose an efficient algorithm for the prefix...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2007-12, Vol.389 (1), p.307-317
Main Authors: Han, Yo-Sub, Wang, Yajun, Wood, Derick
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Miscellaneous
Prefix-free regular languages
Pruned prefix-free languages
Regular-expression matching
String pattern matching
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We explore the regular-expression matching problem with respect to prefix-freeness of the pattern. We prove that a prefix-free regular expression gives only a 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2007.10.017