Checking Time Linearity of Regular Expression Matching Based on Backtracking
スポンサーリンク
概要
- 論文の詳細を見る
Most implementations of regular expression matching in programming languages are based on backtracking. With this implementation strategy, matching may not be achieved in linear time with respect to the length of the input. In the worst case, it may take exponential time. In this paper, we propose a method of checking whether or not regular expression matching runs in linear time. We construct a top-down tree transducer with regular lookahead that translates the input string into a tree corresponding to the execution steps of matching based on backtracking. The regular expression matching then runs in linear time if the tree transducer is of linear size increase. To check this property of the tree transducer, we apply a result of Engelfriet and Maneth. We implemented the method in OCaml and conducted experiments that checked the time linearity of regular expressions appearing in several popular PHP programs. Our implementation showed that 47 of 393 regular expressions were not linear.
- 一般社団法人 情報処理学会の論文
一般社団法人 情報処理学会 | 論文
- Interest Point Detection Based on Stochastically Derived Stability
- Efficient Algorithms for Extracting Pareto-optimal Hardware Configurations in DEPS Framework
- Verification of Substitution Theorem Using HOL (プログラミング Vol.5 No.2)
- Programmable Architectures and Design Methods for Two-Variable Numeric Function Generators
- An Exact Estimation Algorithm of Error Propagation Probability for Sequential Circuits