著者

松原 渉 稲永 俊介 篠原 歩

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.108, no.443, pp.9-16, 2009-02-23

---

平衡直線的プログラム(Balanced Straight line program,BSLP)は単元集合を生成する文脈自由文法とみなすことができ,そこで生成される文字列の長さNは,変数の個数nに対して指数的に長くなりうる.そのため,BSLPによって圧縮表現された文字列に対してnの多項式時間で効率よく処理を行うには,陽に展開することなく処理を行うことが必要不可欠となる.本研究では,BSLPとして表現された文字列の非反復性判定をO(max(n^2,nlog^2N))時間,O(n^2)領域で解くアルゴリズムを示す.