ハイパーグラフのグラフ同型性バグ[2.2.2]

[tamanyan]

現象

以下のプログラムを実行すると、

slim --hl --nd  ../lmntal_program/hlink_bench/hexahedron.lmn
'# of States'(stored)   = 3.
'# of States'(end)      = 0.

のように2状態のはずが3状態になる。

init.

//正六面体
init :- {+!H1,+!H2,+!H3,+!H4,1},{+!H5,+!H1,+!H7,+!H3,0},{+!H2,+!H6,+!H4,+!H8,0},
{+!H6,+!H5,+!H8,+!H7,0},{+!H5,+!H6,+!H1,+!H2,0},{+!H3,+!H4,+!H7,+!H8,0}.

{+!H1,+!H2,+!H3,+!H4,1},{+!H5,+!H1,+!H7,+!H3,0},{+!H2,+!H6,+!H4,+!H8,0},
{+!H6,+!H5,+!H8,+!H7,0},{+!H5,+!H6,+!H1,+!H2,0},{+!H3,+!H4,+!H7,+!H8,0}
:-
{+!H1,+!H2,+!H3,+!H4,0},{+!H5,+!H1,+!H7,+!H3,1},{+!H2,+!H6,+!H4,+!H8,0},
{+!H6,+!H5,+!H8,+!H7,0},{+!H5,+!H6,+!H1,+!H2,0},{+!H3,+!H4,+!H7,+!H8,0}.

原因

分子の探索について、バックトラックが不完全であることが原因です。 現状の実装ではmem_encode.c内のmem_eq_enc_molsが再帰で呼び出されることでバックトラックを行っていますが、このバックトラックが引数で指定されている膜memの中でのみ行われるので、異なる膜間でハイパーリンクが接続されている構造では正しくバックトラックしません。 一意IDについても、同様の理由でバグが出ています。（現在一意IDはハイパーリンクではOFFになっています。）

[tamanyan]

2012-10-03 班ゼミでの議論

エンコードの際に、膜→ハイパーリンクに変換することで解決できるのではないか（もしくはハイパーリンク→膜）

[tamanyan]

2012-07-21

上記のバグを回避することはできますが、バックトラックが起こりやすく、多くの例題で実効性能が非常に悪くなります。(path_mem.lmnやstrcmp_mem.lmn)

バックトラックを回避するためには、ハイパーリンクの探索方法を変える必要があり、バイト列のエンコード・デコード方法から変えるのが良さそうです。

[seelx3]

参考 https://github.com/lmntal/slim/issues/21#issuecomment-1938621247

[nikosai]

#7 はこれと同一の問題とみられるため、こちらに統一します。