正規表現マッチングは文字列を操作するウェブプログラムなど，様々な場面で用いられており，その実装の多くはバックトラックに基づいている．そのため，正規表現マッチングにかかる時間が文字列の長さに関して線形でないことがあり，最悪の場合指数関数時間となる．本発表では正規表現マッチングの時間計算量を判定する手法を提案する．対象の正規表現から先読み付き木トランスデューサを構成する．その先読み付き木トランスデューサから準同型写像や有限遷移系を構成し，それらを用いた遷移過程の中に反復補題が成り立つ遷移過程が存在しているか調べることで計算量を判定することができる．この判定には，AhoとUllmanによる木トランスデューサの増加率の判定法を先読み付き木トランスデューサに拡張したものを利用する．先行研究では，EngelfrietとManethのマクロ木トランスデューサの増加率の判定法を用い，正規表現マッチングの計算時間が入力文字列に対して線形であるかどうかを判定する手法が提案された．本発表で提案する手法は，時間計算量が線形であるかどうかの判定だけでなくO(n2),O(n3),...になることも判定できる．この提案手法をOCamlによって実装し，既存のPHPプログラムで使用されている正規表現を対象に実験を行った．実験の結果，393個中入力文字列の長さに対して338個が線形，44個が2乗，6個が3乗の計算量であると判定された．

Regular expression matching is used in various situations such as web programming. Most of its implementations are based on backtracking. Thus, its execution time may not be linear with respect to the length of an input string. In the worst case, it takes exponential time. In previous research, they proposed a method checking whether the matching of a given regular expression runs in linear time. They translated a regular expression to a tree transducer with regular lookahead and applied the result of Engelfriet and Maneth on proliferation rate of macro tree transducers. In this presentation, we propose a new method of analyzing time complexity of regular matching. This method can check a regular expression matching runs in O(n),O(n2),O(n3),... with respect to the length of input. Instead of the result of Engelfriet and Maneth, we extend the result of Aho and Ullman about proliferation rate of a tree transducer to a tree transducer with lookahead. We obtain a set of homomorphisms from a transducer and then construct a transition system to check whether or not there exist a transition satisfying the condition of the pumping lemma. We implemented this method by OCaml and conducted experiments analyzing execution time of regular expression matching. We applied out method to regular expressions used on existing PHP programs. Our experiments showed that the time complexity of 338 regular expressions are linear, 44 ones are quadratic, and 6 ones are cubic.