SICOMP アクセプト

文字列情報学研究室の論文が国際学術論文誌 SIAM Journal on Computing にアクセプトされました

文字列情報学研究室の坂内英夫准教授、稲永俊介准教授、中島祐人助教、竹田正幸教授、鶴田和弥君 (2013年3月卒業) と、九州工業大学の井智弘助教の論文

"The Runs Theorem",
Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda and Kazuya Tsuruta

が国際学術論文誌、SIAM Journal on Computing にアクセプトされました。この論文では、連 (run) と呼ばれる極大な周期的部分文字列と Lyndon 文字列の新しい関係について報告しています。主な成果としては、

  1. 長さ n の文字列中に含まれる連の最大数 ρ(n) は n 未満であるという「連予想」[Kolpakov & Kuchreov FOCS '99] の肯定的解決
  2. LZ77 分解に基づかない初の線形時間連計算アルゴリズムの提案
  3. その他の連に関係した繰り返し構造に関して、文字列中に含まれる個数に関する上界の改善

などが挙げられます。