Art

J-GLOBAL ID：201602214473796845   Reference number：16A0012055

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

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

Author (2)： KAGAE MASAYUKI (筑波大 大学院システム情報工学研究科) ,  MINAMIDE YASUHIKO (筑波大 システム情報系)
Material： 情報処理学会論文誌トランザクション プログラミング(Web)  (情報処理学会論文誌 プログラミング(Web))
Volume： 8  Issue： 3  Page： 1-10 (WEB ONLY)  Publication year： Sep. 21, 2015 
JST Material Number： U0474A  ISSN： 1882-7802  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： JAPANESE (JA)

Thesaurus term： *regular expression ,  *character string ,  *equivalency ,  inspection ,  *oil displacement ,  converter ,  computation model ,  *character processing ,  nondeterminism ,  streaming
Semi thesaurus term： equivalence checking ,  transducer ,  *文字列置換

JST classification (2)： Mathematical linguistics  (JB05000V) ,  Language processors  (JD03040F)

Reference (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).

Terms in the title (5)： 等価性 ,  正規表現 ,  文字列 ,  置換 ,  応用