バシク行列システムから派生した亜種ルールを分類したものです。目的は、各ルールの違いを比べることです。

The English version is Here.

ルールセット

ルールセット名
作者
初出
定義 bad root
探索
bad part上昇 bad part上昇改変 議論
BM1
バシク
2015.8.21
左隣法 全枝有効方式 改変なし
rTSS
rpakr
2018.5.25
左隣法 全枝有効方式 改変なし
BM1.1[1]
バシク
2016.5.18
上行枝無視方式 全枝有効方式 改変なし
BM2.1
koteitan
2018.3.4
上行枝無視方式 全枝有効方式 改変なし
Bubby3's fix
Bubby3
2018.3.25
上行枝無視方式 全枝有効方式 改変なし
BM2
バシク
2016.6.25
上行枝無視方式 BM2方式 改変なし
BM4
バシク 1st Sep.,'18
上行枝無視方式 上行枝無視方式 改変なし
BM2.3
koteitan

Nish
Ecl1psed

2018.6.18
上行枝無視方式 上行枝無視方式 改変なし
  • BM4 と同等です。
  • BM2 の上昇ルールが難しすぎると思ったので論理的になるように考えて出来ました。
  • 後で聞くと Nish さんと Eclpsed さんも独立に作っていたらしいです。
BM3.1
Nish
2018.7.18
上行枝無視方式 BM2方式 all 1 or (\(a_{xy}\),0,…,0)
  • 現在壊れていると考えられています。
BM3.2
Nish
2018.7.23
上行枝無視方式 上行枝無視方式 all 1 or (\(a'_{xy}\),0,…,0)
  • 現在壊れていると考えられています。
BM3.1.1
Ecl1psed
2018.7.20
上行枝無視方式 BM2方式 all 1 or all 0
  • (2,0)(4,0) のような危険な数列が生成されたりするので、停止しないと予想されているようです。
BM2.2
koteitan
2018.3.8
共通先祖探索 全枝有効方式 改変なし
  • Bubby3さんの解析
  • Nishさんの話では\((0,0,0)(1,1,1)\)が\(\zeta_0\)以下に弱体化しているらしい
  • BM2 の上昇ルールが難しすぎると思ったので bad root 探索ルールの方を改変して出来ましたが、bad part 上昇ルールの方を変えた方がよかったようです。
bad root
bad part(悪い部分)の最左列のことです。

共通ルール

  • バシク行列は要素が自然数である行列と、ブラケットと呼ばれる一つの自然数から成る。
  • バシク行列では\(\begin{pmatrix}c_{11}&c_{21}\\c_{12}&c_{22}\end{pmatrix}\)を\((c_{11},c_{12})(c_{21},c_{22})\)のように列の要素を横に並べて書くことが多いのでこの資料でもそのように表記することにする。
  • \(f(n)\)は自然数から自然数への関数で、BM1, rTSS, BM1.1, Bubby3's fix, BM2, BM4 では\(f(n)=n^2\)、BM2.1, BM2.2, BM2.3 では\(f(n)=n+1\) である。

バシク行列を1段階展開する手順は下記の通りである。

  1. 最右列を \(C=(c_1, c_2, \cdots c_N)\) とする。
  2. \(C\) のすべての要素が \(0\) である場合は、bad root が見つからなかったとして 5 にジャンプ。
  3. \(C\) の非零である最下行のインデックスを \(t\) とする。(\(‪c_t\gt 0\land \forall k(k\gt t\rightarrow c_k=0)‬\))
  4. bad root 探索ルールに従って bad root \(R=(r_1, r_2, \cdots, r_N)\) を決定する。
  5. 最右列 \(C\) を消す。
  6. \([n]\) を \([f(n)]\) に変更する。
  7. bat root が見つからなかった場合は終わる。
  8. bad root \(R\) とそれより右にある列を合わせた行列を bad part \(B=(b_{11},b_{12},\cdots,b_{1N})(b_{21},b_{22},\cdots,b_{1N})\cdots(b_{L1},b_{L2},\cdots,b_{LN})\) とする。
  9. この後、bad root がコピーされるが、コピーの際の値の上昇値として
    \(\Delta=(\delta_{11}, \cdots, \delta_{1N})\cdots(\delta_{L1},\cdots,\delta_{LN})\)を次のように定義する。\(\forall x~\delta_{xy}=\begin{cases}c_y-r_y&(y\lt t)\\0&(y \geq t)\end{cases}\)
  10. 上昇を行うかどうかのフラグとして、上昇検討行列 \(A'=(a'_{11}, a'_{12}, \cdots, a'_{1N})(a'_{21}, a'_{22}, \cdots, a'_{2N})\cdots(a'_{L1}, a'_{L2}, \cdots, a'_{LN})\) を上昇ルールに従って定義する。
  11. 上昇改変ルールに従って、上昇検討行列 \(A'\) から上昇行列 \(A\) を求める。
  12. ブラケット\(n\) の値に従って次に定義する \(B_1, B_2, \cdots, B_n\) をもとの行列に順に右に連結する。
  • \(B_1 = B + A \otimes \Delta\)
  • \(B_{k+1} = B_k + A \otimes \Delta\)
  • \(\otimes\) は行列と行列の要素積で、

\((a_{11},\cdots, a_{1N})\cdots(a_{L1},\cdots, a_{LN}) \otimes (b_{11},\cdots, b_{1N})\cdots(b_{L1},\cdots, b_{LN}) \)
\(= (a_{11}b_{11},\cdots, a_{1N}b_{1N})\cdots(a_{L1}b_{L1},\cdots, a_{LN}b_{LN})\) 以上。

以上の展開を繰り返し、行列がなくなったときのブラケットの値が元のバシク行列に対応する巨大数となる。

bad root 探索ルール

左隣法

  1. \(t\) とそれより上の全ての行 \(y \leq t\) で \(m_y > c_y\) を満たし、かつ \(c\) より左にある列 \(M=(m_1, \cdots, m_N)\) が存在すれば、その最右列 \(M\) を bad root \(R\) とする。なければ bad root は見つからなかったとする。

上行枝無視方式 (Upper-Branch-Ignoring-Model)

  • 要素 \(c\) 自身、または、\(c\) の直系先祖の親を、「\(c\) の直系先祖」と再帰的に定義する。
  • 要素 \(c\) に対して、
    • \(c\) と同じ行にある
    • \(c\) より左にある
    • \(c\) より値が小さい
    • 最上行にあるか、または、\(c\) のひとつ上の要素の直系先祖のいずれかと同じ列にある

をすべて満たす最右の要素 \(m\) を \(c\) の親と定義する。

  1. \(C\) の非零最下行要素 \(c_t\) の親がいる場合は、その親のいる列を bad root \(R\) とする。親がいない場合は bad root は見つからなかったとする。

共通先祖探索 (concestor method)

  • 要素 \(c\) 自身、または、\(c\) の直系先祖の親を、「\(c\) の直系先祖」と再帰的に定義する。
  • 要素 \(c\) に対して、
    • \(c\) と同じ行にある
    • \(c\) より左にある
    • \(c\)より値が小さい

をすべて満たす最右の要素 \(m\) を \(c\) の親と定義する。

  1. 非零最下行 \(t\) とそれ以上の全ての行 \(y \geq t\) において、 \(m_y\) が \(c_y\) の直系先祖であるような列 \(M=(m_1, \cdots, m_N)\) が存在すれば、その中の最右列を bad root \(R\) とする。そのような列が無ければ bad root は見つからなかったとする。

bad part 上昇ルール

全枝有効方式

  • \(\forall x,y(a'_{xy}=1)\)

BM2 方式

\(a'_{xy}\) を下記で定める。

\[p(x)=\max\left\{k|k \lt x \land b_{k1} \lt b_{x1}\right\}\] \[\forall y \left(a'_{1y}=1\right)\] \[\forall x\gt 1,~y (a'_{xy}=1 \leftrightarrow a'_{p(x)y}=1 \land b_{1y} \lt b_{xy}) \]

\(p(x)\) は列 \(x\) の親の列を表す。これは最上行のみで決まる。

2行目は bad root は常に上昇することを表している。

3行めは \(b_{xy}\) は「\(b_{xy}\) と同じ行にあり親の列にある要素が上昇する」かつ「\(b_{xy}\) が \(b_{xy}\)と同じ行にあり bad root の列にある要素の値よりも大きい」を満たす時その時のみ上昇することを表す。


上行枝無視方式 (Upper-Branch-Ignoring-Model)

  • 要素 \(c\) 自身、または、\(c\) の直系先祖の親を、「\(c\) の直系先祖」と再帰的に定義する。
  • 要素 \(c\) に対して、
    • \(c\) と同じ行にある
    • \(c\) より左にある
    • \(c\) より値が小さい
    • 最上行にあるか、または、\(c\) のひとつ上の要素の直系先祖のいずれかと同じ列にある

をすべて満たす最右の要素 \(m\) を \(c\) の親と定義する。

  • \(r_y\) が \(b_{xy}\) の直系先祖であるような \(x, y\) の組について \(a'_{xy}=1\)、それ以外の時 \(a'_{xy}=0\)

上昇改変ルール

改変なし

\(\forall xy (a_{xy}=a'_{xy})\)


All 1 or (\(a'_{xy}\),0,…,0)

ある列 \(x\) について、下記のように \(a'_{xy}\) から \(a_{xy}\) を定める。

  • もし\(\forall y \leq t(a'_{xy}=1)\) なら \(\forall y(a_{xy}=1)\)、そうでなければ、\(a_{x1}=a'_{xy}\) かつ \(\forall y \gt 1(a_{xy}=0)\)。

All 1 or All 0

ある列 \(x\) について、下記のように \(a'_{xy}\) から \(a_{xy}\) を定める。

  • もし\(\forall y\leq t(a'_{xy}=1)\) なら \(\forall y(a_{xy}=1)\)、そうでなければ、\(\forall y(a_{xy}=0)\)。

注釈

  1. 正式名が無かったので、BM1.1というのはこのページで私が勝手に仮につけた名前です。
特に記載のない限り、コミュニティのコンテンツはCC-BY-SA ライセンスの下で利用可能です。