相似変換を用いた有限オートマトンの決定性および非決定性最小化
スポンサーリンク
概要
- 論文の詳細を見る
有限オートマトン (FA) を離散時間の動的システムと捉え, ブール半環B (=(B, +,・), B={0, 1}) という代数系を用いることで現代制御理論の分野と同様な状態空間モデルを構成でき, FAの可到達性, 可観測性から最小化という概念が定義できることが示されている. ここでFAの最小化とは与えられたFAの入出力関係を変化させず, 状態数を最小にすることである. 最小化には決定性と非決定性の最小化があり, 決定性最小化とは与えられたFAを決定性FA (DFA) のクラスで, 非決定性最小化とは, 非決定性FA (NFA) のクラスで最小化することである. しかしNFAに関しては, オートマトン理論においてもその最小化の方法は知られていない. 本報告ではTA_k=A^^-_kTという相似変換を用いたFAの決定性および非決定性の最小化について検討する. 相似変換を用いることでFAの最小化をTによるFAの写像と捉えることができる.
- 社団法人電子情報通信学会の論文
- 1997-03-06
著者
-
渡辺 浩司
福山大学人間文化学部
-
福永 邦雄
大阪府立大学大学院工学研究科電気・情報系専攻
-
福永 邦雄
大阪府立大学大学院工学研究科
-
猪飼 武夫
大阪府立大学大学院工学研究科
-
渡辺 浩司
大阪府立大学工学部
関連論文
- 等式および不等式制約最適化のための力学系
- トリプレックスRNS浮動小数点表示の精度保証付き数値計算への応用
- 連続フレームからの抽出画像の重ね合わせによるロバストな道路標識認識手法(画像認識,コンピュータビジョン)
- 連続フレームからの抽出画像の重ね合わせによる障害物遮蔽を考慮した道路標識認識(ITS画像処理, データベース, 一般)
- サッカーの放送型映像における試合中断区間に注目したイベント推定(一般セッション4(映像処理1),文字・文書の認識・理解)
- ミーリー機械の初期状態推定器
- 3角パッチ表現による3次元物体のコントラスト情報量に基づく視点および光源位置の選択(一般セッション9)
- 3角パッチ表現による3次元物体のコントラスト情報量に基づく視点および光源位置の選択(一般セッション3,三次元画像,多視点画像)
- キーストロークの統計情報を利用した個人認証手法の提案
- 独居高齢者の行動パターンに注目した非日常状態の検出
- 移動カメラの自己位置および移動物体の追跡と視覚障害者に対する危険通知への応用(ヒューマンコミュニケーショングループ (HCG) シンポジウム)
- 移動カメラの自己位置および移動物体の追跡と視覚障害者に対する危険通知への応用
- I-057 ウェアラブルカメラによる人物行動の認識と複数メディアを用いた要約表現(I.画像認識・メディア理解)
- 人物の位置・姿勢に注目した行動パターンの学習・認識と非日常状態検出への応用(画像認識,コンピュータビジョン)
- ウェアラブルカメラを用いた人物行動のマルチモーダル表現(複合現実感とインタラクション)
- 形状情報量の分布に基づくシーンの映像表現(複合現実感とインタラクション)
- I_068 スポーツ中継映像におけるRGBヒストグラムとDCTを用いたショット分割(I分野:画像認識・メディア理解)
- I_001 視点情報量に基づく3次元物体の代表的景観の選択(I分野:画像認識・メディア理解)
- LL-017 統計的手法を用いた計算機ログからの異常検出(L分野:ネットワークコンピューティング)
- D-12-13 カメラの動きを用いたサッカーの中継映像におけるボールの追跡(D-12. パターン認識・メディア理解, 情報・システム2)
- SVMを用いたネットワークトラヒックからの異常検出
- B-7-10 One-class SVMによるネットワークトラフィックからの異常検出(B-7. 情報ネットワーク)
- D-12-131 部分画像と色・輪郭類似度による物体認識(D-12. パターン認識・メディア理解B)
- マウス操作の特徴を用いた個人識別システム
- サッカー中継映像からのフィールド上の選手位置推定(複合現実感とインタラクション)
- D-12-156 歩行動作の時空間画像からの人物識別
- D-12-112 サッカーの中継映像における複数選手の追跡
- ネットワーク・サーバ運用監視支援システム
- D-12-103 サッカーのTV中継映像における選手の追跡
- 解空間の逐次削減によるスケジューリング手法
- ループフォールディングスケジューリングにおけるレジスタ間データ転送コストの最小化
- ループフォールディングスケジューリングにおけるレジスタ間データ転送コストの最小化
- 力学モデルスケジューリング手法の高速化
- ボトムアップ手法によるループフォールディングスケジューリング
- 異なるハードウェアコスト評価を用いたループフォールディングの効率化
- 解空間の縮小を用いたスケジュール手法
- 解空間の縮小を用いたスケジュール手法
- データフローグラフ上のパターンマッチングによるデータパスアロケーション
- データ依存関係を考慮したPath-Based Scheduling
- 力学モデルスケジューリング手法の高速化
- 接続確率に基づくアロケーション手法
- レジスタ-レジスタ間データ転送を考慮したパイプライン方式データパスのスケジューリング法
- 接続確率に基づくアロケーション手法
- 接続確率に基づくアロケーション手法
- バス接続によるデータパスアロケーション
- 整数計画法を用いたCMOS機能セルの最適設計手法
- シミュレーティド・アニーリングを用いたテクノロジーマッピング
- 視聴覚融合を用いたHMM音声認識
- カオスニューラルネットのダイナミクスと最小値探索
- 3角パッチ表現による3次元物体のコントラスト情報量に基づく視点および光源位置の選択(一般セッション3,三次元画像,多視点画像)
- キーストロークの統計情報を利用した個人認証手法の提案
- キーストロークの統計情報を利用した個人認証手法の提案
- 運転者の目領域抽出による視線推定
- 受講者の心理状態を考慮した講義の自動撮影
- 状況理解と映像評価に基づく講義の知的自動撮影
- 視聴者の心理状態を考慮したシーンの映像化手法
- SD-5-3 状況理解と映像評価による知的自動撮影システム : 複数カメラを用いた講義映像生成
- 状況理解と映像評価を考慮した講義の知的自動撮影
- D-12-73 講義者の行動認識に基づく講義撮影の自動化
- 輪郭線の階層表現による物体認識の一手法
- ニューラルネットワークを用いた画像構造に基づく物体認識
- 輪郭線の構造木表現とその物体認識への応用
- HMM音声認識における視聴覚融合手法
- 負の自己結合を有する離散値型ニューラルネットワークとその応用
- 時間遅れニューラルネットワークを用いた電力ケーブルの故障原因診断システム
- 有限状態機械の状態推定と予測
- Ho-Kalmanアルゴリズムを用いた実数有限オートマトンの最小実現
- 有限状態機械の状態観測器
- 順序機械の状態観測器
- Ho-Kalmanアルゴリズムによる決定性有限オートマトンの最小実現
- 相似変換を用いた有限オートマトンの決定性および非決定性最小化
- マトロイド理論に基づく有限オートマトンの非決定性最小化
- ネットワークと図書館
- 非決定性オートマトンの状態モデル表現
- シミュレーティド・アニーリングを用いたテクノロジーマッピング
- D-12-39 移動ロボットによる人物の動作認識と自然言語表現(D-12. パターン認識・メディア理解,一般セッション)
- LI-007 身体の軌跡情報の解析に基づいた動作と動作対象の統合的認(I分野:画像認識・メディア理解)
- 協調型ベイジアンネットワークを用いた動作と動作対象の統合的認識(テーマ関連セッション(2))
- 動作と物体の統合的認識とそのモデル化(テーマ関連セッション(2))
- 実数値記憶パターンの動的連想記憶モデル
- Hopfield-上坂最適化法の一般化と内点法
- 画像・図と言語の統合
- プロセス代数と様相論理を融合した並行システムの仕様記述
- 解釈の曖昧性を考慮した図と説明テキストの統合理解
- 解釈の曖昧性を考慮した図とテキストの統合理解
- 文書画像構造解析のためのインクリメンタルな知識獲得
- 動的機能のモデルに基づく物体の機能認識
- ハードウェア設計仕様における自然言語記述の一階論理に基づく状況的・動的解釈
- 構文・意味解析を用いた文字認識後処理法
- 文書構造解析のための文書例からのレイアウト構造知識の自動獲得
- I-038 三角パッチ表現向き形状情報量による3次元物体の視点選択(I分野:画像認識・メディア理解)
- D-11-18 3次元物体の三角パッチ表現における形状情報量と視点決定(D-11. 画像工学A(画像基礎・符号化), 情報・システム2)
- D-11-16 3次元物体の形状および色情報量に基づく視点決定(D-11. 画像工学A(画像基礎・符号化), 情報・システム2)
- A-4-4 時変未知システムに対するテーラ近似フィルタ(A-4. ディジタル信号処理)
- 混合制約最適化のための勾配力学系と0-1最適化への応用
- チューリング機械のアナログ動的モデル
- 決定性有限オートマトンの正準分解とそのアルゴリズム
- オートマトンの抽象族の状態モデル表現とエージェントオートマトン
- 一階論理の形式化によるオブジェクト指向モデルの記述言語と推論系
- 有限状態システムに関する説明テキストの一階論理に基づく文脈理解