WEKO3
アイテム
Checking Time Linearity of Regular Expression Matching Based on Backtracking
https://ipsj.ixsq.nii.ac.jp/records/102175
https://ipsj.ixsq.nii.ac.jp/records/102175c19b932d-f4e3-4352-a736-16caee49fe93
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TPRO0703002.pdf (289.7 kB)
|
Copyright (c) 2014 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2014-07-14 | |||||||
| タイトル | ||||||||
| タイトル | Checking Time Linearity of Regular Expression Matching Based on Backtracking | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Checking Time Linearity of Regular Expression Matching Based on Backtracking | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | [通常論文] regular expression, tree transducer, linear size increase | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| Department of Computer Science, University of Tsukuba | ||||||||
| 著者所属 | ||||||||
| Department of Computer Science, University of Tsukuba | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, University of Tsukuba | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, University of Tsukuba | ||||||||
| 著者名 |
Satoshi, Sugiyama
Yasuhiko, Minamide
× Satoshi, Sugiyama Yasuhiko, Minamide
|
|||||||
| 著者名(英) |
Satoshi, Sugiyama
Yasuhiko, Minamide
× Satoshi, Sugiyama Yasuhiko, Minamide
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Most implementations of regular expression matching in programming languages are based on backtracking. With this implementation strategy, matching may not be achieved in linear time with respect to the length of the input. In the worst case, it may take exponential time. In this paper, we propose a method of checking whether or not regular expression matching runs in linear time. We construct a top-down tree transducer with regular lookahead that translates the input string into a tree corresponding to the execution steps of matching based on backtracking. The regular expression matching then runs in linear time if the tree transducer is of linear size increase. To check this property of the tree transducer, we apply a result of Engelfriet and Maneth. We implemented the method in OCaml and conducted experiments that checked the time linearity of regular expressions appearing in several popular PHP programs. Our implementation showed that 47 of 393 regular expressions were not linear. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Most implementations of regular expression matching in programming languages are based on backtracking. With this implementation strategy, matching may not be achieved in linear time with respect to the length of the input. In the worst case, it may take exponential time. In this paper, we propose a method of checking whether or not regular expression matching runs in linear time. We construct a top-down tree transducer with regular lookahead that translates the input string into a tree corresponding to the execution steps of matching based on backtracking. The regular expression matching then runs in linear time if the tree transducer is of linear size increase. To check this property of the tree transducer, we apply a result of Engelfriet and Maneth. We implemented the method in OCaml and conducted experiments that checked the time linearity of regular expressions appearing in several popular PHP programs. Our implementation showed that 47 of 393 regular expressions were not linear. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464814 | |||||||
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO） 巻 7, 号 3, p. 1-11, 発行日 2014-07-14 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7802 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
