Theoretical Computer Science アクセプト

文字列情報学研究室の中島祐人君、岡部駿志君 の論文が国際学術論文誌 Theoretical Computer Science にアクセプトされました。

文字列情報学研究室の中島祐人君 (執筆時 D3 - 2017年3月卒業)、岡部駿志君 (当時 M2 - 2015年3月卒業) の論文

"Inferring Strings from Lyndon Factorization,

Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda."

が国際学術論文誌 Theoretical Computer Science にアクセプトされました。この論文では、Lyndon 分解の逆問題を考えています。逆問題とは、文字列構造が与えられたときに、その文字列構造を持つ文字列を推測する問題です。逆問題は、接尾辞木や接尾辞配列など様々な文字列構造に対して盛んに研究が行われています。Lyndon 分解とよばれる文字列の辞書式順序を捉えた分解に対しての逆問題に初めて取り組み、関連する複数の問題に対して効率的なアルゴリズムや列挙解のコンパクトな表現方法を提案しています。またこの論文は、MFCS 2014 にアクセプトされた論文の拡張版となっています。