文字列の辞書式順序の組合せ論とその応用

点击翻译按钮获取中文摘要

本年度の主な成果は以下のとおりである。1) 文字列に部分列として含まれる最長の Lyndon 語を求める O(n^3) 時間・O(n) 領域のアルゴリズムを提案した。また、文字列の各接頭辞に対して順にこれを計算するオンラインな設定において、O(n^3σ) 時間・領域のアルゴリズムを提案した。ここで、σ はアルファベットサイズである。また、更に問題を拡張し、二つの文字列に共通して部分列として含まれる最長の Lyndon 語を計算する O(n^4σ) 時間・O(n^3) 領域のアルゴリズムを示した。これらの成果は国際会議 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022) にて発表し、ベストペーパー賞を受賞した。2) 辞書式圧縮に関連する文字列の圧縮性指標のうち、計算が NP-困難であることが知られている最小文字列アトラクタのサイズ γ、最小双方向マクロスキームのサイズ b、及び最小の直線的プログラム（Straight Line Program)のサイズ g それぞれについて、MAX-SAT 問題に帰着し、MAX-SAT ソルバを利用することで、ある程度大きな文字列についても現実的な時間で厳密な値が計算できることを示し、これらの値を計算する初めての非自明な実装を提案した。また、この実装を利用することで γ の圧縮感度の下界を 2 から 2.5 に改善する文字列のクラスを発見した。