Streaming String Transducerの等価性判定と正規表現による文字列置換への応用

• Item type: Trans(1)
• 公開日: 2015-09-21
• タイトル: Streaming String Transducerの等価性判定と正規表現による文字列置換への応用
• タイトル / 言語: en
• タイトル: Equivalence Checking of Streaming String Transducers and Its Application to Regular Expression Replacement
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [通常論文] 正規表現，ストリーミング文字列トランスデューサ，等価性判定
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 筑波大学大学院システム情報工学研究科
• 著者所属: 筑波大学システム情報系
• 著者所属(英): en
• 著者所属(英): Graduate School of Systems and Information Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Information and Systems, University of Tsukuba
• 著者名: 加賀江, 優幸; 南出, 靖彦
• 著者名(英): Masayuki, Kagae; Yasuhiko, Minamide
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 文字列から新たな文字列を生成する計算モデルとしてAlurとCernyによるストリーミング文字列トランスデューサ（Streaming String Transducer: SST）がある．SSTは，文字を受け取るごとに文字列を保存できる変数の内容を更新し，最終的には変数の内容を用いて出力文字列を構成するトランスデューサである．本研究では，関数的非決定性ストリーミング文字列トランスデューサ（関数的SST）の等価性判定を正規表現による文字列置換の等価性判定に応用する．ここで，関数的とは非決定性であっても出力がたかだか1つであることを示す．関数的SSTの等価性判定問題の決定可能性はAlurらによって証明されている．しかしながら，判定方法は複雑であり直感的な理解が困難であった．そこで，本論文では関数的SSTの等価性判定アルゴリズムの簡略化について述べる．また，本アルゴリズムの実装および実験結果についても述べる．正規表現による文字列置換はグループ変数にマッチした箇所を複数回出力することができることから有限状態トランスデューサでは模倣できない．そこで，本論文では正規表現による文字列置換を関数的SSTで模倣することにより，関数的SST上の検証問題に帰着させる．最終的には，関数的SSTの等価性判定アルゴリズムを正規表現による文字列置換の等価性判定に応用する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 8, 号 3, p. 1-10, 発行日 2015-09-21
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会