PSC 2017 アクセプト

文字列情報学研究室の中島助教、稲永准教授、坂内准教授、竹田教授の論文が国際会議 PSC 2017 にアクセプトされました

文字列情報学研究室の中島助教、稲永准教授、坂内准教授、竹田教授、北海道大学の高木拓也氏の論文

"On Reverse Engineering the Lyndon Tree"
Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda.

が国際会議 PSC 2017 にアクセプトされました。
この論文では、Lyndon 文字列を表現する二分木構造である Lyndon 木の逆問題を考えています。逆問題とは、文字列構造が与えられたときに、その文字列構造を持つ文字列を推測する問題です。逆問題は、接尾辞木や接尾辞配列など様々な文字列構造に対して盛んに研究が行われています。入力として二分木が与えられたときに、その木を Lyndon 木としてもつような Lyndon 文字列について、その Lyndon 文字列のアルファベットサイズの上界と下界を与えました。

PSC 2017 は8月28日~30日に、チェコのプラハにて開催されます。