Prefix-free regular languages and pattern matching
| Autor: | Derick Wood, Yajun Wang, Yo-Sub Han |
|---|---|
| Rok vydání: | 2007 |
| Předmět: |
Matching (statistics)
Theoretical computer science Optimal matching General Computer Science Pruned prefix-free languages Data_CODINGANDINFORMATIONTHEORY String searching algorithm Regular-expression matching Theoretical Computer Science Prefix Regular language 3-dimensional matching String pattern matching Prefix-free regular languages Regular expression Pattern matching Algorithm Mathematics Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 389(1-2):307-317 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2007.10.017 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect