講演名 | 2011-12-16 双対型positionオートマトンを用いたコンパクトなDFA表現 山本 博章, 中村 彰吾, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 正規表現のための照合アルゴリズムは,正規表現を決定性有限オートマトン(DFA)に変換すれば,検索は高速に行うことができる.しかし,最悪の場合は,DFAのサイズが元の正規表現の長さの指数的になってしまう.長さmの正規表現に対し,一般にDFAのサイズは(m+1)2^<2m+1>|Σ|ビット必要とする.NavarroとRaffinotは,positionオートマトンを利用して,(m^^~+1)2^ |
抄録(英) | This paper introduces an automaton model called a dual position automaton (a dual PA), and then gives a bit-parallel algorithm for generating a dual PA from a regular expression (RE). For any RE r over an alphabet Σ, our translation algorithm generates a dual PA consisting of m^^~(m^^~+1) bits in O(m^^~「m^^~/w」) time and space, where w is the length of a computer word, m^^~=Σ_m_a and m_a is the number of occurrences of an alphabet symbol a in r. Furthermore, we give a method to construct a compact DFA representation from a dual PA. This DFA representation requires only (m^^~+1)Σ_2^ |
キーワード(和) | 正規表現 / positionオートマトン / 決定性有限オートマトン |
キーワード(英) | regular expression / dual-position automaton / deterministic finite automaton |
資料番号 | COMP2011-36 |
発行日 |
研究会情報 | |
研究会 | COMP |
---|---|
開催期間 | 2011/12/9(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Theoretical Foundations of Computing (COMP) |
---|---|
本文の言語 | JPN |
タイトル(和) | 双対型positionオートマトンを用いたコンパクトなDFA表現 |
サブタイトル(和) | |
タイトル(英) | A Compact DFA representation using dual-position automata |
サブタイトル(和) | |
キーワード(1)(和/英) | 正規表現 / regular expression |
キーワード(2)(和/英) | positionオートマトン / dual-position automaton |
キーワード(3)(和/英) | 決定性有限オートマトン / deterministic finite automaton |
第 1 著者 氏名(和/英) | 山本 博章 / Hiroaki YAMAMOTO |
第 1 著者 所属(和/英) | 信州大学工学部 Faculty of Engineering, Shinshu University |
第 2 著者 氏名(和/英) | 中村 彰吾 / Syougo NAKAMURA |
第 2 著者 所属(和/英) | 信州大学大学院工学系研究科 Graduate School, Shinshu University |
発表年月日 | 2011-12-16 |
資料番号 | COMP2011-36 |
巻番号(vol) | vol.111 |
号番号(no) | 360 |
ページ範囲 | pp.- |
ページ数 | 7 |
発行日 |