Article,
Prefix-free regular languages and pattern matching
Theor. Comput. Sci., 389 (1-2): 307--317 (2007)
DOI: http://dx.doi.org/10.1016/j.tcs.2007.10.017
Abstract
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.
