Baum-Sweet文字列

初期文字 \(A\) , \(B\) , \(C\) , \(D\) による \(n\) 番目のBaum-Sweet文字列
n =
A =
B =
C =
D =
A,B →
C,D →
・BS(n) = dummy
・BS(n) = dummy
注 ：\(n\) を大きい数にするとおかしくなります．(入力制限で \(n<20\) としています)

定義

\(n\) 番目の Baum–Sweet文字列 (Baum–Sweet Word) \(BS_n\) を以下のような定義で生成する． \(BS_n\) は， \(BS_{n-1}\) に対して次の規則に従った変換を行うことにより生成できる． ただし， \(BS_0 = A\) とする．

  • \(A → AB\)
  • \(B → CB\)
  • \(C → BD\)
  • \(D → DD\)

この生成された文字列に対して以下の変換を行ったものがBaum–Sweet sequenceとなる．

  • \(A → 1\)
  • \(B → 1\)
  • \(C → 0\)
  • \(D → 0\)

性質

アルゴリズム集

参考文献

Baum, Leonard E., and Melvin M. Sweet. "Continued fractions of algebraic power series in characteristic 2." The Annals of Mathematics 103.3 (1976): 593-610.

Allouche, Jean-Paul, and Jeffrey Shallit. Automatic sequences: theory, applications, generalizations. Cambridge university press, 2003.