やったこと

ReDoS

一日時間があったのでReDoSについて考えていた。

多分、なんらかの方法でバックトラックの構造を保ったNFAに変換して、それに対して指数時間・多項式時間であることの判定をすればいいのではないかと思う。
まあそのバックトラックの構造を保ったNFAというのが難しいのだが‥‥。

大体分かったつもりなのでやっていく。やっていきたい。