Han, Yo-Sub Wang, Yajun Wood, Derick 2024-01-21T00:03:05Z 2024-01-21T00:03:05Z 2021-09-02 2007-12-10 0304-3975 https://pubs.kist.re.kr/handle/201004/133886 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. (c) 2007 Elsevier B.V. All rights reserved. English ELSEVIER SCIENCE BV GENERALIZED AUTOMATA ALGORITHM SEARCH Prefix-free regular languages and pattern matching Article 10.1016/j.tcs.2007.10.017 1 THEORETICAL COMPUTER SCIENCE, v.389, no.1-2, pp.307 - 317 THEORETICAL COMPUTER SCIENCE 389 1-2 307 317 scie scopus 000251695800025 2-s2.0-36149000603 Computer Science, Theory & Methods Computer Science Article GENERALIZED AUTOMATA ALGORITHM SEARCH string pattern matching regular-expression matching prefix-free regular languages pruned prefix-free languages