Baum-Sweet文字列¶
初期文字 \(A\) , \(B\) , \(C\) , \(D\) による \(n\) 番目のBaum-Sweet文字列
・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.