Minimum Consistent-DFA生成問題の厳密解法に対するハイブリッドアプローチ
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,ラベル付き記号列集合から最小状態数の決定性有限状態オートマトン (DFA) を効率よく生成する手法について述べる.この問題は,NP 困難な問題と知られているが,近年の SAT ソルバーの効率化によって,専用のアルゴリズムに匹敵する計算速度が得られたことが報告された.本稿では,この手法をさらに発展させるため,対称性除去のための最大クリークを MILP ソルバーで発見する方法を導入する.また,ヒューリスティックに発見した DFA を上界,最大クリークを下界としたアルゴリズムを提案する.数値実験の結果,ベンチマーク問題に対して従来手法の 50% の計算時間で結果が得られることがわかった.
- 2011-02-28
著者
-
相澤 彰子
国立情報学研究所
-
乾 伸雄
総合研究大学院大学複合科学研究科
-
相澤 彰子
国立情報学研究所コンテンツ科学研究系
-
乾 伸雄
総合研究大学院大学 国立東京工業高等専門学校
-
相澤 彰子
東京大学,国立情報学研究所
-
相澤 彰子
国立情報学研
-
相澤 彰子
The University of Tokyo, UT:National Institute of Informatics, NII
関連論文
- 商品および商品についての情報源に対する信頼の統計的ネットワークモデル
- Grozea, C., Gehl, C. and Popescu, M., ENCOPLOT: Pairwise Sequence Matching in Linear Time Applied to Plagiarism Detection, Proc. 3rd Pan Workshop, Uncovering Plagiarism, Authorship and Social Software Misuse, pp. 10-18, 2009, 剽窃の検出技術
- 2. 座談会 女性会員を取り巻く環境はこんなです(女性会員に期待する)
- 帰納推論による時系列データからの関係構造の抽出スキル解析に向けたプラットフォーム
- D-4-13 TV Searchbar: Webからの放送コンテンツの参照(D-4. データ工学,一般セッション)
- 学術情報の統合に向けた大規模リンケージ基盤の構築
- 3.アカデミックリンケージ : 膨大な学術情報へのアクセスを支援するリンケージ基盤(パートII:情報分野研究者のためのオンリーワン共有イノベーションプラットフォーム,情報爆発時代におけるわくわくするITの創出を目指して)
- 6J-4 情報爆発時代のための制約つきクラスタリングを用いた制約つきフィードバック手法の提案(情報爆発時代における情報検索・推薦技術およびWebコミュニティ分析,一般セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- ナーススケジューリング問題における混合整数線形計画問題と充足可能性判定問題による厳密解法の比較
- A22 KAKEN βと研究者リゾルバーαの情報構造 : KAKEN β1.12と研究者リゾルバーα1.12(セッションA2(情報システムの構築1),一般発表概要,第5回情報プロフェッショナルシンポジウム)
- D-5-8 情報圧縮に基づくデータ間類似度によるパーソナライゼーション(D-5. 言語理解とコミュニケーション,一般セッション)
- 走査型半導体露光装置における移動順最適化(機械力学,計測,自動制御)
- D-5-7 マルチモーダル情報を用いた放送番組からの人物相関図生成(D-5. 言語理解とコミュニケーション,一般セッション)
- 完全N部グラフ構造を用いた単語の多義性獲得(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(一般及び自動推論)
- ナーススケジューリング問題における混合整数線形計画問題と充足可能性判定問題による厳密解法の比較(論文・研究レポート)
- 小特集「国際会議で見つけたオススメ論文」にあたって
- 発話を意識した文推薦システムの構築と評価
- 発話を意識した文推薦システムの構築と評価
- 沈黙のWeb(編集委員今年の抱負2009:経糸から横糸まで)
- 論文情報ナビゲータの構築(セッション5 : 文書データベース)
- 論文情報ナビゲータの構築(セッション5 : 文書データベース)
- 情報検索における圧縮距離の適用に関する考察
- 3Q-8 視線検出装置を用いた研究者の論文の読み方の解析(情報抽出,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- D-5-8 視線情報によるユーザプロファイルの文書推薦における有用性(D-5.言語理解とコミュニケーション,一般セッション)
- 視線情報を用いたユーザプロファイル獲得と文書推薦
- 4U-8 検索用キーフレーズの解析及び抽出手法の提案(文書の分類と検索,学生セッション,人工知能と認知科学)
- 土木関連用語辞典の見出し語の分析と検索システムにおける活用に関する考察(辞書と辞典)
- 土木関連用語辞典の見出し語の分析と検索システムにおける活用に関する考察(辞書と辞典)
- 著者キーワード中での共起に基づく専門用語間の関連度計算法
- 名詞と動詞の依存関係を利用したテキストからのIS-A関係の発見方法
- F-020 テキストコーパスからの上下関係抽出(F分野:人工知能・ゲーム)
- D-011 数式とその周辺情報を利用した数式概念検索の実現(D分野:データベース,一般論文)
- 3Q-1 数式概念検索のための情報抽出手法に関する検討(情報抽出,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- B-005 類似性を考慮した数式検索手法の提案(ソフトウェア,一般論文)
- D-006 視聴中の番組を起点とした関連番組検索(データベース,一般論文)
- 3Q-9 名前同定のためのSVM特徴素の抽出と適用(情報抽出,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- 大規模データベースを利用したリンケージシステムの提案と実装
- 1ZM-3 ネットワーク構造からみたQ&Aコミュニティの分析(ソーシャルネットワーク,学生セッション,コンピュータと人間社会,情報処理学会創立50周年記念)
- 6X-6 自由対話実現のための自動文章生成モデルの提案(対話,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- D-021 遺伝的プログラミングを用いたキーワード抽出尺度の探索と進化(データベース,一般論文)
- レコード同定問題に関する研究の課題と現状(データ工学論文)
- 大規模テキストコーパスを用いた語の類似度計算に関する考察(自然言語,新しいパラダイムの中での分散システム/インターネット運用・管理)
- 情報学の明日を考える (特集 情報学の第4ステージ)
- Helmer, S., Measuring the structural similarity of semistructured documents using entropy(情報の似ている度合いを圧縮プログラムで計測), Proc. 33rd International Conference on Very Large Data Bases, pp.1022-1032, 2007
- 特集「情報の信頼性評価」にあたって
- テキストと「意味の解像度」
- 複数書誌データベース統合における重複エントリーの高速検出法(セッション5 : 文書データベース)
- 多重ネットワークの調査とシミュレーション (「知能と社会・ネットワーク」および一般発表)
- 共起に基づく類似性尺度(自然言語とコンピュータ)
- Webコーパスを用いた語の類似度計算に関する考察
- Pasca, M. and Durme, B. V.:What you seek is what you get: Extraction of class attributes from query logs, Proc. 20th Int. Joint Conf. Artificial Intelligence (IJCAI-07), pp.2832-2837(2007)
- テキストを媒体とする情報の伝達をめぐって(編集委員2007年の抱負)
- テキストを媒体とする情報の伝達をめぐって
- Webコーパスを用いた語の類似度計算に関する考察 (「Web Intelligence」および一般発表)
- 類語関係抽出タスクにおけるコーパス規模拡大の影響(言語モデル・単語)
- 類語関係抽出タスクにおけるコーパス規模拡大の影響(言語モデル・単語)
- I_070 Proxy上でのWeb画像分類(I分野:画像認識・メディア理解)
- 語義の違いを検出するための大規模コーパス処理手法の検討(「自動化:推論,発見,学習,データマイニング」及び一般)
- Minimum Consistent-DFA生成問題の厳密解法に対するハイブリッドアプローチ
- Web上の文書を対象とした産学連携研究開発情報抽出の試み
- 多クラス文書分類問題におけるZiv-Merhav Crossparsingの適用と評価
- 複数書誌データベース統合における重複エントリーの高速検出法(セッション5 : 文書データベース)
- 異種データベース間でのレコード照合に関する研究動向
- NTCIR-9総括と今後の展望
- NTCIR-9総括と今後の展望
- 日英言語横断検索における関連性の重ね合わせモデルの効果(情報の検索とテストコレクション)
- 関連性の重ね合わせモデルを用いた日英言語横断検索
- 近未来チャレンジ : 2004-2005(近未来チャレンジ卒業記念解説)
- 2-1 閲覧中のWebコンテンツを起点とした関連番組検索(第2部門 メディア処理2)
- 自然言語処理と計算代数の接合による数学問題へのアプローチ(ロボットは東大に入れるか?)
- 2012年度人工知能学会全国大会を終えて
- SATソルバーを用いた最小無矛盾DFAの生成
- 「2012年度全国大会速報論文特集」にあたって
- 3-4 Wikipediaの変更履歴を利用した関連番組検索(第3部門 インタフェース・その他)
- 「種と類」の話
- E-031 A Method for Corresponding Paragraphs with Sentences in Academic Paper's Abstract
- E-030 Towards the Integration of Natural Language and Eye Tracking Information for Predicting Comma Placement in Chinese Sentence
- D-025 更新履歴による注目度を利用した番組検索結果のリランキング(クラスタリング,D分野:データベース)
- 研究者同定とその応用 : 統計分野と材料科学分野を例として
- 自然言語処理と計算代数の接合による数学問題へのアプローチ
- 調査データに基づく社会構造変化の抽出 集団間のネットワークの定性分析と帰納論理の適用:集団間のネットワークの定性分析と帰納論理の適用
- 2012年度人工知能学会全国大会を終えて
- Twitter上の「おはよう」を例とした崩れた異表記の認識(地域情報&ソーシヤルメデイア,第4回集合知シンポジウム)
- 発話を意識した文推薦システムの構築と評価 (自然言語処理(NL) Vol.2011-NL-200)
- 発話を意識した文推薦システムの構築と評価 (情報基礎とアクセス技術(IFAT) Vol.2011-IFAT-101)
- 情報検索における圧縮距離の適用に関する考察 (自然言語処理(NL) Vol.2010-NL-199)
- 盛り上がり時間帯におけるツイートの言語的特性の解析
- 盛り上がり時間帯におけるツイートの言語的特性の解析
- 実文書を自然言語処理技術と適切に繋ぐ技術の重要性
- Retweetに着目した広がりやすいTweetの特徴分析
- 汎用エージェントの理論的枠組み : Marcus Hutterが提唱するAIXIの紹介(汎用人工知能(AGI)への招待)