文献

J-GLOBAL ID：201402221821698594   整理番号：14A0161156

正規表現の接頭語及び接尾語を利用した新たなオートマトンの構成法

A New Automaton Construction using Prefixes and Suffixes of Regular Expressions

著者 (1件)： YAMAMOTO Hiroaki (Shinshu Univ., Nagano, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 113  号： 371(COMP2013 38-59)  ページ： 99-106  発行年： 2013年12月13日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 正規表現から有限オートマトンを作成するための新たな手法を提案する。提案法は,与えられた正規表現に対し,最初に,各状態が正規表現の接頭語及び接尾語でラベル付けされたラベル付きThompsonオートマトンを作成する。その後,各状態を接頭語及び接尾語のラベルにしたがって,等価な状態を統合することにより,有限オートマトンを構成する。提案法で得られる新たなオートマトンは,O(m²)の時間及び領域で構成することができ,その状態数は,従来のequationオートマトンの状態数以下になる。(著者抄録)

シソーラス用語： *正規表現 ,  文法 ,  文書 ,  *有限オートマトン ,  *パターンマッチング
準シソーラス用語： プレフィックス ,  ラベル付け【文書】 ,  接尾辞

分類 (1件)： オートマトン理論  (JB04000O)

タイトルに関連する用語 (2件)： 正規表現 ,  オートマトン