[#20227] dyna_vars problem? — Tanaka Akira <akr@...17n.org>

しばらく前から、稀に Ruby が core を吐くという問題を追いかけているので

15 messages 2003/05/19
[#20234] Re: dyna_vars problem? — matz@... (Yukihiro Matsumoto) 2003/05/19

まつもと ゆきひろです

[#20236] Re: dyna_vars problem? — Tanaka Akira <akr@...17n.org> 2003/05/19

In article <1053363181.529491.30320.nullmailer@picachu.netlab.jp>,

[ruby-dev:20218] Re: /()*\1/ =~ ""

From: kkosako@...
Date: 2003-05-19 09:37:46 UTC
List: ruby-dev #20218
> -----Original Message-----
> From: Tanaka Akira [mailto:akr@m17n.org]
> ...
> backreference が入ると NP 完全になるので、もし効率良くできたら世界的に
> 有名になれるんじゃないですかね。
> http://perl.plover.com/NPC/
> 
> さて、とすると、
> 
> (1) 指数関数的な時間を使って全部解く
> (2) 適当にあきらめる
> 
> という選択肢があるわけですが、もし (2) をとるなら、どういうようにあき
> らめるかが問題になります。あきらめかたをいかにわかりやすくするかという
> か。
> 
> なんとなく、根拠はないんですが、繰り返しの中身は空文字列にマッチしない
> 、
> というのがいいかなぁ、と思い始めて来たんですが、どんなもんでしょう?

その方向で良ければ、実装上もありがたい気がします。

無意味な例ですが、以下の場合もマッチしないということで納得して頂けますか?
/()*/ =~ ""
--
小迫@出向中

In This Thread

Prev Next