決定性有限オートマトンによる正規表現の貪欲な照合

Material type: その他

Author: 奥居, 哲ほか

Publisher: 中部大学情報科学研究所

Publication date: 2013-03

Material Format: Digital

Capacity, size, etc.: -

NDC: -

View All

Notes on use

Note (General)：: 出版タイプ： AMtype:報告正規表現の貪欲な文字列照合を可能にする決定性オートマトン(DFA)を構築する手法について述べる.構築されるDFA は,正規表現から構築される古典的なDFA と異なり,NFA 状態の列をDFA 状態とみなし,もとの正規表現の部分式の情報を遷移毎に保持している.このため,...

Search by Bookstore

Holdings of Libraries in Japan

This page shows libraries in Japan other than the National Diet Library that hold the material.

List of Cooperating Institutions and Databases

Please contact your local library for information on how to use materials or whether it is possible to request materials from the holding libraries.

other

Chubu University Digital Archives
Digital
You can check the holdings of institutions and databases with which Institutional Repositories DataBase(IRDB)(Institutional Repository) is linked at the site of Institutional Repositories DataBase(IRDB)(Institutional Repository).
Chubu University Digital Archives

Search by Bookstore

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Digital

Material Type: その他
Title: 決定性有限オートマトンによる正規表現の貪欲な照合
Author/Editor: 奥居, 哲
増田, 拓也
藤田, 佳宏
鈴木, 大郎
Author Heading: 奥居, 哲
増田, 拓也
藤田, 佳宏
鈴木, 大郎
Publication, Distribution, etc.: 中部大学情報科学研究所
Publication Date: 2013-03
Publication Date (W3CDTF): 2013
Alternative Title: ケッテイセイユウゲンオートマトンニヨルセイキヒョウゲンノドンヨクナショウゴウ
DFA-based Implementation of Greedy Regular Expression Matching
Periodical title: 情報科学リサーチジャーナル
No. or year of volume/issue: 20
Volume: 20
Pages: 97-104
ISSN (Periodical Title): ISSN : 1340-2935
Target Audience: 一般
Note (General): 出版タイプ： AM
type:報告
正規表現の貪欲な文字列照合を可能にする決定性オートマトン(DFA)を構築する手法について述べる.構築されるDFA は,正規表現から構築される古典的なDFA と異なり,NFA 状態の列をDFA 状態とみなし,もとの正規表現の部分式の情報を遷移毎に保持している.このため,貪欲な部分照合を行い各部分式毎の照合を得ることが可能になる.非決定性オートマトン(NFA)に基づく従来手法では照合の各ステップの計算コストがNFA のサイズに依存して増加するのにたいし,提案手法では定数になる.提案手法の(実行時の)最悪の場合の計算コストはO(n)(n は照合される文字列の長さ)であり,バックトラックを用いる手法やNFA を直接用いる手法と比較して改善されている.
Access Restrictions: インターネット公開
Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
Original Data Provider (Database): 中部大学 : 中部大学学術情報リポジトリ