- 著者
- 加賀江 優幸 南出 靖彦
- 雑誌
- 情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)
- 巻号頁・発行日
- vol.8, no.3, pp.1-10, 2015-09-21
文字列から新たな文字列を生成する計算モデルとしてAlurとCernyによるストリーミング文字列トランスデューサ(Streaming String Transducer: SST)がある.SSTは,文字を受け取るごとに文字列を保存できる変数の内容を更新し,最終的には変数の内容を用いて出力文字列を構成するトランスデューサである.本研究では,関数的非決定性ストリーミング文字列トランスデューサ(関数的SST)の等価性判定を正規表現による文字列置換の等価性判定に応用する.ここで,関数的とは非決定性であっても出力がたかだか1つであることを示す.関数的SSTの等価性判定問題の決定可能性はAlurらによって証明されている.しかしながら,判定方法は複雑であり直感的な理解が困難であった.そこで,本論文では関数的SSTの等価性判定アルゴリズムの簡略化について述べる.また,本アルゴリズムの実装および実験結果についても述べる.正規表現による文字列置換はグループ変数にマッチした箇所を複数回出力することができることから有限状態トランスデューサでは模倣できない.そこで,本論文では正規表現による文字列置換を関数的SSTで模倣することにより,関数的SST上の検証問題に帰着させる.最終的には,関数的SSTの等価性判定アルゴリズムを正規表現による文字列置換の等価性判定に応用する.