やったこと

グラフ

やっと一段落した気がする。
それなりにがんばれた。

ReDoS

拡張正規表現——ようするに後方参照がある正規表現について考えていた。

[Freydenberger 2013] によると、キャプチャが1変数につき1箇所しかなくて、かつ繰り返しの中に後方参照が無いような場合でも、equivalence や regularity が undecidable らしい。

Freydenberger, Dominik D. "Extended regular expressions: Succinctness and decidability." Theory of Computing Systems 53.2 (2013): 159-193.

これは Turing 機械の実行過程をいい感じにエンコードした列について、そうでないものを受理する拡張正規表現が作れることを利用しているっぽい。
ただ、否定を取っているのが重要で、ambiguity の場合は Post の対応問題でどっちも受理されるとしたら解になるようにして undecidable であることを導くので、なんか上手くいかない気もする。
どうしたらいいんだ。何も分からん。