文献

J-GLOBAL ID：201002266284915103   整理番号：10A1081667

正規表現からコンパクトなオートマトンを構成するための一手法

A method to construct a compact automata from regular expressions

著者 (2件)： 坂田俊則 (信州大 工) ,  山本博章 (信州大 工)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 110  号： 214(COMP2010 24-30)  ページ： 31-38  発行年： 2010年09月22日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 正規表現から構成されるコンパクトな非決定性有限オートマトンとしてfollowオートマトンやequationオートマトンというものが知られている。本論文は,equationオートマトンを構成するための手法として,Thompsonオートマトンから作成するためのアルゴリズムを与える。本アルゴリズムは,正規表現の長さをmとしたとき,O(m²)時間で走る。また,正規表現に現れるアルファベット記号の数をsとしたとき,構成されるequationオートマトンは,状態数が高々s+1,状態遷移の数が高々s(s+1)となる。さらに,followオートマトンと組み合わせることによりさらにコンパクトな有限オートマトンを得ることができることを示す。(著者抄録)

シソーラス用語： *正規表現 ,  *有限オートマトン ,  ツリー構造 ,  状態遷移図 ,  *計算機アルゴリズム ,  *非決定性オートマトン ,  構文分析 ,  同値関係 ,  コンパクト性 ,  CPU時間 ,  配列
準シソーラス用語： 構文木 ,  計算時間

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

引用文献 (18件)：

• ANTIMIROV, V. Partial derivative of regular expressions and finite automaton construction. Theoret. Comput. Sci. 1996, 155, 291-319
• BILLE, P. New Algorithms for Regular Expression Matching. Proc. of ICALP 2006. 2006, 643-654
• BRUGGEMANN-KLEIN, A. Regular expressions into finite automata. Theoret. Comput. Sci. 1993, 120, 197-213
• CHANG, C. H. From regular expressions to DFA's using compressed NFA's. Theoret. Comput. Sci. 1997, 178, 1-36
• CHAMPARNAUD, J.-M. Evaluation of three implicit structures to implement nondeterministic automata from regular expressions. Internat. J. Found. Comput. Sci. 2002, 13, 1, 99-113

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