A Polynomial Time Match Test for Large Classes of Extended Regular Expressions

http://dx.doi.org/10.1007/978-3-642-18098-9_26

* なし
| なし
.* と後方参照だけがある。

/(.*)(.*)\2\1/

こんな正規表現で、キャプチャと参照の間に挟まる参照/変数の重複を除いた数が定数kで押さえられていれば、多項式時間 $O(n^{4+k})$ でマッチできる。

上のだと \1 の間には \2 だけが挟まっていて 1 通りしかないので $O(n^5)$ あれば。

/(.*)(.*)\2\1(.*)\3\1/

も1と数える。\1 がない区間に\1以外が何個あるか。

それはLarge Classというには制約しすぎ、そりゃできるだろう…という印象。

証明にでてきたJanus automatonというものを使う、という証明の方向性は新しいのかも知れないし、この先があるかもしれない、けど結果はあまり新しくない気がする。

別証明を考える

k+1変数のIO Macro Grammarで書けることを示す。

A( vars(x_1 ... x_{k+1}) ) → x_1 ... x_{k+1}
x_1 = x_i where 2≦i≦k+2 なら
  B( vars(x_2 ... x_{k+2}) ) → A( vars(x_2 ... x_{k+1}) ) x_{k+2}
x_1 がどれとも違う変数なら
  B( vars(x_2 ... x_{k+2}) ) → A( .*, vars(x_2 ... x_{k+1}) ) x_{k+2}
x_2 = x_i where 3≦i≦k+3 なら
  C( vars(x_3 ... x_{k+3}) ) → B( vars(x_3 ... x_{k+2}) ) x_{k+3}
x_2 がどれとも違う変数なら
  C( vars(x_3 ... x_{k+3}) ) → B( .*, vars(x_3 ... x_{k+2}) ) x_{k+3}
...

というルールでよい。k文字以上離れて同じ文字が出現することはないので、その分くらい変数で持ち回っておけば共有できる。

あー、k文字以上離れて、ではなくk変数以上、なのでちょっと嘘だけど、正確には vars(...) が x_左を足しても増えないならそのまま、増えるなら .* で増やす、で k+1は超えない。