平衡直線的プログラムで圧縮された文字列の非反復性検証アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
平衡直線的プログラム(Balanced Straight line program,BSLP)は単元集合を生成する文脈自由文法とみなすことができ,そこで生成される文字列の長さNは,変数の個数nに対して指数的に長くなりうる.そのため,BSLPによって圧縮表現された文字列に対してnの多項式時間で効率よく処理を行うには,陽に展開することなく処理を行うことが必要不可欠となる.本研究では,BSLPとして表現された文字列の非反復性判定をO(max(n^2,nlog^2N))時間,O(n^2)領域で解くアルゴリズムを示す.
- 2009-02-23
著者
関連論文
- 無限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 間引きを用いたパス技術の自律学習(学習・推論,学生セッション,人工知能と認知科学)
- 電子マネーシステムの価値保存形式を考慮したモデル化(Session 3)
- 圧縮文字列上での $q$-gram 頻度の高速な計算方法 (計算機科学とアルゴリズムの数理的基礎とその応用)
- DS-1-12 文字列に含まれる連構造(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- イベント列データにおけるVLDCエピソード生成モデル (「メディアとAI」および一般)
- 半導体歩留り解析に回帰木分析を適用するための仮説検証手法の提案
- 半導体歩留り解析のための回帰木に基づく仮説検証手法の提案
- 非線形コラージュシステムにおける文字列パターン照合
- 非線形テキストにおける最長共通部分文字列・部分列アルゴリズム
- 役を構成するゲームに対する効率的な行動決定アルゴリズムの提案
- マルチトラック文字列の順列パターン照合と索引構造 (Theoretical Foundations of Computing)
- 半導体歩留り解析のための回帰木に基づく仮説検証手法の提案
- 圧縮文字列に対する省メモリなパターンマッチアルゴリズム (Theoretical Foundations of Computing)
- 圧縮文字列に対する省メモリなパターンマッチアルゴリズム
- マルチトラック文字列の順列パターン照合と索引構造
- マルチトラックデータ上の近似順列パターン照合と索引構造
- 文字列に含まれる連の最大指数和の解析 : n=57までの厳密値と新たな下界2.03696の発見
- 高階圧縮の高速化と効率の良い符号化