@article{oai:ipsj.ixsq.nii.ac.jp:00145137,
 author = {加賀江, 優幸 and 南出, 靖彦 and Masayuki, Kagae and Yasuhiko, Minamide},
 issue = {3},
 journal = {情報処理学会論文誌プログラミング（PRO）},
 month = {Sep},
 note = {文字列から新たな文字列を生成する計算モデルとしてAlurとCernyによるストリーミング文字列トランスデューサ（Streaming String Transducer: SST）がある．SSTは，文字を受け取るごとに文字列を保存できる変数の内容を更新し，最終的には変数の内容を用いて出力文字列を構成するトランスデューサである．本研究では，関数的非決定性ストリーミング文字列トランスデューサ（関数的SST）の等価性判定を正規表現による文字列置換の等価性判定に応用する．ここで，関数的とは非決定性であっても出力がたかだか1つであることを示す．関数的SSTの等価性判定問題の決定可能性はAlurらによって証明されている．しかしながら，判定方法は複雑であり直感的な理解が困難であった．そこで，本論文では関数的SSTの等価性判定アルゴリズムの簡略化について述べる．また，本アルゴリズムの実装および実験結果についても述べる．正規表現による文字列置換はグループ変数にマッチした箇所を複数回出力することができることから有限状態トランスデューサでは模倣できない．そこで，本論文では正規表現による文字列置換を関数的SSTで模倣することにより，関数的SST上の検証問題に帰着させる．最終的には，関数的SSTの等価性判定アルゴリズムを正規表現による文字列置換の等価性判定に応用する．, A streaming string transducer (SST) proposed by Alur and Cerny is a powerful computation model from strings to strings. A SST equips with several variables that store strings and each transition updates the contents of the variables. We apply functional nondeterministic streaming string transducers (Functional SST) to model regular expression replacement in programming languages. Alur et al. showed the decidability of equivalence checking of Functional SST. However, they did not show the details of their algorithm and no implementation and experimental results are reported, as long as we know. In this paper, we reformulate and describe the details of equivalence checking of Functional SST. We also report our implementation and experimental results. Regular expression replacement cannot be precisely modeled by a finite state transducer. It is because it may output a string matched with a group variable more than once. We construct Functional SST that simulates regular expression replacement and apply equivalence checking of Functional SST to equivalence checking of regular expression replacement.},
 pages = {1--10},
 title = {Streaming String Transducerの等価性判定と正規表現による文字列置換への応用},
 volume = {8},
 year = {2015}
}