{"id":195818,"updated":"2025-01-19T22:55:10.906072+00:00","links":{},"created":"2025-01-19T01:00:42.351372+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00195818","sets":["934:935:9619:9764"]},"path":["9764"],"owner":"44499","recid":"195818","title":["Derivatives of Regular Expressions with Lookahead"],"pubdate":{"attribute_name":"公開日","attribute_value":"2019-05-21"},"_buckets":{"deposit":"8a5e9656-f12e-4937-9543-aabcf0b86148"},"_deposit":{"id":"195818","pid":{"type":"depid","value":"195818","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"Derivatives of Regular Expressions with Lookahead","author_link":["467654","467655","467656","467657"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Derivatives of Regular Expressions with Lookahead"},{"subitem_title":"Derivatives of Regular Expressions with Lookahead","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[通常論文] regular expressions with lookahead, derivatives","subitem_subject_scheme":"Other"}]},"item_type_id":"3","publish_date":"2019-05-21","item_3_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"School of Computing, Tokyo Institute of Technology"},{"subitem_text_value":"School of Computing, Tokyo Institute of Technology"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"School of Computing, Tokyo Institute of Technology","subitem_text_language":"en"},{"subitem_text_value":"School of Computing, Tokyo Institute of Technology","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/195818/files/IPSJ-TPRO1202004.pdf","label":"IPSJ-TPRO1202004.pdf"},"date":[{"dateType":"Available","dateValue":"2021-05-21"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TPRO1202004.pdf","filesize":[{"value":"212.7 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"15"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"2fb908ed-f3f0-4192-986c-35110fa99038","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2019 by the Information Processing Society of Japan"}]},"item_3_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Takayuki, Miyazaki"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Yasuhiko, Minamide"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Takayuki, Miyazaki","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"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":"Lookahead is an extension of regular expressions that has been adopted in many implementations and is widely used. Lookahead represents what is allowed as the rest of input. Morihata developed a conversion from regular expressions with lookahead (REwLA) to deterministic finite automata by extending Thompson's construction. In this paper, we develop a conversion from REwLA to deterministic finite automata by extending derivatives of regular expressions. First, we formalize the semantics of REwLA. An REwLA has information about the rest of the input, so the definition of the semantics of REwLA is not languages but structures different from those of regular expressions. Thus, we introduce languages with lookahead as sets of pairs of strings with several operations and define the semantics of REwLA as languages with lookahead. Next, we define two kinds of left quotient for languages with lookahead and give corresponding derivatives. Then, we show that the types of expressions obtained by repeatedly applying derivatives are finite under some equivalence relation and give a conversion to deterministic finite automata. We also show that the semantics of REwLA is a finite union of sets of the form A × B, where A and B are regular languages.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.27(2019) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Lookahead is an extension of regular expressions that has been adopted in many implementations and is widely used. Lookahead represents what is allowed as the rest of input. Morihata developed a conversion from regular expressions with lookahead (REwLA) to deterministic finite automata by extending Thompson's construction. In this paper, we develop a conversion from REwLA to deterministic finite automata by extending derivatives of regular expressions. First, we formalize the semantics of REwLA. An REwLA has information about the rest of the input, so the definition of the semantics of REwLA is not languages but structures different from those of regular expressions. Thus, we introduce languages with lookahead as sets of pairs of strings with several operations and define the semantics of REwLA as languages with lookahead. Next, we define two kinds of left quotient for languages with lookahead and give corresponding derivatives. Then, we show that the types of expressions obtained by repeatedly applying derivatives are finite under some equivalence relation and give a conversion to deterministic finite automata. We also show that the semantics of REwLA is a finite union of sets of the form A × B, where A and B are regular languages.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.27(2019) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌プログラミング（PRO）"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2019-05-21","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"2","bibliographicVolumeNumber":"12"}]},"relation_version_is_last":true,"weko_creator_id":"44499"}}