文字列に含まれる連の最大指数和の解析 : n=57までの厳密値と新たな下界2.03696の発見
スポンサーリンク
概要
- 論文の詳細を見る
連とは,文字列に含まれる周期的な部分文字列であり,その周期性が左右に延長不可能なものをいう.近年,長さnの文字列に含まれる連の最大数についての研究が活発になされている.本論文では,連の数え方の一つである指数和に着目し,長さnのバイナリ文字列に含まれる連の指数和の最大値σ_2(n)について,枝刈りを用いて計算を高速化することにより得られたn=57までの計算結果を示す.また,連の指数和の最大値σ(n)について,これまでに知られている最良の下界は2.03525nであったが,我々は文字列を生成する準同型写像を探索することにより,新たな下界2.03696nを発見した.
- 2013-04-17
著者
-
篠原 歩
東北大学大学院情報科学研究科
-
成澤 和志
九州大学大学院システム情報科学府情報処理学専攻
-
草野 一彦
東北大学大学院情報科学研究科
-
成澤 和志
東北大学大学院情報科学研究科
-
奥田 遼介
東北大学大学院情報科学研究科
関連論文
- 無限n-ボナッチ文字列の繰り返し構造について
- 基本形式体系に対する非終端記号の導入 (コンピュテーション)
- 圧縮文字列における最長共通部分文字列および回文を求める多項式時間アルゴリズム
- 平衡直線的プログラムで圧縮された文字列の非反復性検証アルゴリズム
- 半導体歩留り解析へのデータマイニング適用手法の提案
- 文字列の繰り返し構造の平均解析 (理論計算機科学の深化と応用)
- 連を多く含む文字列発見のための探索的手法 (理論計算機科学の深化と応用)
- 接尾辞配列による効率的な文字列上の同値類計算
- 部分文字列の数え上げによるブログスパムの検出(マイニングとフィルタリング)
- 部分文字列の数え上げによるブログスパムの検出(マイニングとフィルタリング)
- 間引き：ロボットのスキル発見における評価の削減手法
- 移調を許した圧縮文字列照合アルゴリズム
- 基本形式体系に対する非終端記号の導入
- 長さ優先置換による文字列圧縮の線形時間アルゴリズム(文字列アルゴリズム)
- A-025 非可逆圧縮を用いた類似性指標と画像検索への応用(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- A-024 信頼区間上限の不確実性サンプリングへの応用(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- 5N-2 文字列に含まれる繰り返し構造の頻度について(アルゴリズム,学生セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- DS-1-6 例数制限付き教示の複雑さ(DS-1.計算理論における学生の研究パワー:COMP学生シンポジウム,シンポジウムセッション)
- DS-1-5 非終端記号を導入した基本形式体系の言語記述力について(DS-1.計算理論における学生の研究パワー:COMP学生シンポジウム,シンポジウムセッション)
- 置換のランク付けに対する$O$($n$log log$n$)ビット領域の線形時間アルゴリズム (理論計算機科学の深化と応用)
- 例数制限付き教示の複雑さ (理論計算機科学の深化と応用)
- 3R-2 通信規約学習の拡張による協調精度の向上(学習,学生セッション,人工知能と認知科学)
- 1V-3 間引きを用いたパス技術の自律学習(学習・推論,学生セッション,人工知能と認知科学)
- DS-1-12 文字列に含まれる連構造(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- イベント列データにおけるVLDCエピソード生成モデル (「メディアとAI」および一般)
- 半導体歩留り解析に回帰木分析を適用するための仮説検証手法の提案
- 半導体歩留り解析のための回帰木に基づく仮説検証手法の提案
- 役を構成するゲームに対する効率的な行動決定アルゴリズムの提案
- マルチトラック文字列の順列パターン照合と索引構造 (Theoretical Foundations of Computing)
- 半導体歩留り解析のための回帰木に基づく仮説検証手法の提案
- 圧縮文字列に対する省メモリなパターンマッチアルゴリズム (Theoretical Foundations of Computing)
- 組込環境用プロセス仮想マシンの実装とETロボコンへの適用 (制御研究会 : ETロボコン2012におけるソフトウェア設計モデル)
- 圧縮文字列に対する省メモリなパターンマッチアルゴリズム
- マルチトラック文字列の順列パターン照合と索引構造
- 種々のパターン照合問題に対するポジションヒープの構築(一般)
- 2-E-7 SAT ソルバを用いた学位論文審査の時間割作成システムの試作(スケジュール(1))
- マルチトラックデータ上の近似順列パターン照合と索引構造
- 文字列に含まれる連の最大指数和の解析 : n=57までの厳密値と新たな下界2.03696の発見
- 高階圧縮の高速化と効率の良い符号化