文献

J-GLOBAL ID：201602214473796845   整理番号：16A0012055

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

Equivalence Checking of Streaming String Transducers and Its Application to Regular Expression Replacement

著者 (2件)： 加賀江優幸 (筑波大 大学院システム情報工学研究科) ,  南出靖彦 (筑波大 システム情報系)
資料名： 情報処理学会論文誌トランザクション プログラミング(Web)  (情報処理学会論文誌 プログラミング(Web))
巻： 8  号： 3  ページ： 1-10 (WEB ONLY)  発行年： 2015年09月21日 
JST資料番号： U0474A  ISSN： 1882-7802  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 文字列から新たな文字列を生成する計算モデルとしてAlurとCernyによるストリーミング文字列トランスデューサ(Streaming String Transducer:SST)がある。SSTは,文字を受け取るごとに文字列を保存できる変数の内容を更新し,最終的には変数の内容を用いて出力文字列を構成するトランスデューサである。本研究では,関数的非決定性ストリーミング文字列トランスデューサ(関数的SST)の等価性判定を正規表現による文字列置換の等価性判定に応用する。ここで,関数的とは非決定性であっても出力がたかだか1つであることを示す。関数的SSTの等価性判定問題の決定可能性はAlurらによって証明されている。しかしながら,判定方法は複雑であり直感的な理解が困難であった。そこで,本論文では関数的SSTの等価性判定アルゴリズムの簡略化について述べる。また,本アルゴリズムの実装および実験結果についても述べる。正規表現による文字列置換はグループ変数にマッチした箇所を複数回出力することができることから有限状態トランスデューサでは模倣できない。そこで,本論文では正規表現による文字列置換を関数的SSTで模倣することにより,関数的SST上の検証問題に帰着させる。最終的には,関数的SSTの等価性判定アルゴリズムを正規表現による文字列置換の等価性判定に応用する。(著者抄録)

シソーラス用語： *正規表現 ,  *文字列 ,  *等価性 ,  検査 ,  *置換【油層】 ,  変換器 ,  計算モデル ,  *文字処理 ,  非決定性 ,  ストリーミング
準シソーラス用語： 等価性チェック ,  トランスデューサ ,  *文字列置換

分類 (2件)： 数理言語学  (JB05000V) ,  言語プロセッサ  (JD03040F)

引用文献 (10件)：

• Alur, R. and Cerny, P.: Expressiveness of streaming string transducers, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), LIPIcs, Vol.8, pp.1-12(2010).
• Alur, R. and Deshmukh, J.V.: Nondeterministic streaming string transducers, Proc. 38th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, Vol.6756, pp.1-20 (2011).
• Alur, R. and Černý, P.: Streaming transducers for algorithmic verification of single-pass list-processing programs, Proc. 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, pp.599-610 (2011).
• Courcelle, B.: Monadic second-order definable graph transductions: A survey, Theoretical Computer Science, Vol.126, No.1, pp.53-75 (1994).
• Engelfriet, J. and Maneth, S.: The Equivalence Problem for Deterministic MSO Tree Transducers Is Decidable, FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, Vol.3821, pp.495-504 (2005).

タイトルに関連する用語 (5件)： 等価性 ,  正規表現 ,  文字列 ,  置換 ,  応用