6月くらいに考えた Upper-Branch-Ignoring モデル (上枝無視モデル) というバシク行列(BM4)のヒドラ表現を紹介します。(バシク行列の展開ルールと、この記事内の数式については、バシク行列の数式的定義 を見てください。バシクさんのオリジナルの定義はこちらにあります。)

先行研究

BM4 の bad root 探索の方法については、Bubby3 さん、Ecl1psed276 さん、Alemagno12 さんが下記の記事で分かりやすく説明してくれています。

これらの方法は内容は同じで、Ecl1psed276 さん、Alemagno12 さんはこの方法を sequence reduction method (数列削除法) と呼び、Bubby3 さんは upper-branch removing method (上枝削除法)と呼んでいます。

Bubby3 さんは下記のように (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1) という行列を例に upper-branch removing method を使った bad root の見つけ方を説明してくれています。

  1. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
  2. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
  3. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
  4. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
  5. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
  6. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
  7. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)

この方法は、上記のように注目ノードよりも高さが低いノードを探しながら、スキップされたノードのある列を数列から消していく方法となっています。

この説明は非常にシンプルなのですが、探索の間中、削除操作によって行列がどんどん動的に変わっていくので、上昇行列 \(A_{xy}\) を求める時と次の展開をするときに行列をたくさん書かないといけなくなります。

提案

そこで、この数列削除法の動的な挙動を静的に表せる図の書き方を考えたのが Upper-Branch-Ignoring モデル です。

Fig.1 Upper-Branch-Ignoring モデル

Upper-Branch-Ignoring モデルの図は、行列の行数 \(Y\) と同じ数のヒドラから成っています。各ヒドラの各ノードの高さは行列 \(\mathrm{S}\) の要素の値 \(S_{xy}\) と一致します。各辺は親ノード \(P_y(x)\) への繋がりを表しています。その接続は最上行のヒドラは原始数列数のヒドラ表現そのものですが、2行目以降は異なってきます。

Fig.2 Mistake

2行目以降のヒドラの接続は、上の行の影響を受けるのです。

下記が下の行のヒドラの接続の書き方です。

Fig.3 ヒドラの書き方

Fig.3-1 の赤色('子'と呼びましょう)の親を探して線を接続することを考えます。

まず、と同じ列にあるひとつ上の行のヒドラのノードを緑のようにマークします(Fig.3-1)。次にその直系先祖全て \(\forall a(P_{y-1})^a(x)\) をマークします(Fig.3-2)。最後にその上の直系先祖同じ列にある当該行のヒドラのノードだけを見ながら(Fig.3-3)、の高さよりも低い高さにある最右のノードを探して線を繋ぎます(Fig.3-4)。これが \(P_{y}(x)\)です。

この図は静的なので、bad root 探索と上昇行列の決定に便利です。下記はその方法です。

Fig.4 bad root探索、上昇行列、コピー

これは (0,0,0)(1,1,1)(2,0,0)(1,1,1) の例です。 (これは BM1 が停止しない有名な行列です) 行列の bad root \(r\) は最右の刈られる子 \(X-1\) の非零最下行 \(t\) の要素 (\(\mathrm{S}_{X-1}=\)(1,1,1)) の親 \(P_t(X-1)\) と定義されます。

上昇行列 \(A_{xy}\) は、それらの再帰的な子孫(\(\{\forall x|\forall ar=P^{a}_y(r+x)\}\)) です。以上です。非常に簡素に終わりました。ピンクのノード は bad root の子孫ではないので、上昇せず、元の高さをキープしたままコピーされます。

また、コピーのときも、この親の木構造をそのままコピーすればいいので楽です。次の展開の時に再度親の接続の解析をする必要はありません。

このように、Upper-Branch-Ignoring モデルを使うと bad root 探索、上昇ノードの決定、コピーが簡単かつ静的に分析&実行できます。

続く?

この図を使って、また別の非常に面白いバシク行列の特性を見つけました。その話はまた別の記事で…

表記例

下記は Upper-Branch-Ignoring モデルを使った図の例です。

Fig.5-1 例:(BM1 が停止しない行列)

Fig.5-2 例:(BM2 が停止しない行列)

参考文献

特に記載のない限り、コミュニティのコンテンツはCC-BY-SA ライセンスの下で利用可能です。