{"updated":"2025-01-21T10:55:50.102692+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00102175","sets":["934:935:7419:7624"]},"path":["7624"],"owner":"11","recid":"102175","title":["Checking Time Linearity of Regular Expression Matching Based on Backtracking"],"pubdate":{"attribute_name":"公開日","attribute_value":"2014-07-14"},"_buckets":{"deposit":"95a61d99-e62b-4a50-b288-c2d7644277c9"},"_deposit":{"id":"102175","pid":{"type":"depid","value":"102175","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"Checking Time Linearity of Regular Expression Matching Based on Backtracking","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Checking Time Linearity of Regular Expression Matching Based on Backtracking"},{"subitem_title":"Checking Time Linearity of Regular Expression Matching Based on Backtracking","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[通常論文] regular expression, tree transducer, linear size increase","subitem_subject_scheme":"Other"}]},"item_type_id":"3","publish_date":"2014-07-14","item_3_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Department of Computer Science, University of Tsukuba"},{"subitem_text_value":"Department of Computer Science, University of Tsukuba"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Department of Computer Science, University of Tsukuba","subitem_text_language":"en"},{"subitem_text_value":"Department of Computer Science, University of Tsukuba","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/102175/files/IPSJ-TPRO0703002.pdf"},"date":[{"dateType":"Available","dateValue":"2016-07-14"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TPRO0703002.pdf","filesize":[{"value":"289.7 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"15"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"4f47f108-03db-4252-aec5-f9ff867a68ab","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2014 by the Information Processing Society of Japan"}]},"item_3_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Satoshi, Sugiyama"},{"creatorName":"Yasuhiko, Minamide"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Satoshi, Sugiyama","creatorNameLang":"en"},{"creatorName":"Yasuhiko, Minamide","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_3_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11464814","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_3_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7802","subitem_source_identifier_type":"ISSN"}]},"item_3_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"11","bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌プログラミング（PRO）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2014-07-14","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicVolumeNumber":"7"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"created":"2025-01-18T23:47:30.136979+00:00","id":102175,"links":{}}