二値アルファベット上の有限オートマトンの等価変換と状態数解析
スポンサーリンク
概要
- 論文の詳細を見る
任意の非負整数αに対して,n状態の非決定性有限オートマトン(NFA)で,その等価な最小決定性有限オートマトン(DFA)が2^n-α状態を持つものが存在するか,という問題はIwamaら[3]によって提起された。本稿では,n%ge;11,α%le;3n-3,⌊(α-1)/3⌋が奇数でかつnと互いに素である,という条件を満たすnとαに対して,n状態NFAで,その等価な最小DFAが2^n-α状態を持つものが存在することを示す.また,α%le;4n-5の範囲の4の倍数でないαに対しても,同様のNFAの存在を示す.
- 2008-03-07
著者
関連論文
- 球面幾何学に基づく新たなジャグリング
- Spherical Juggling におけるパターン表記法
- 部分空間の関連性を利用した四次元空間の動的可視化ソフトウェア
- ハノイの塔問題に対する再帰方程式の一般化とその厳密解析
- 二値アルファベット上の有限オートマトンの等価変換と状態数解析
- 文理複合型情報系組織におけるプログラミング教育の実践例(プログラミング,何をどう教えているか)
- プログラミング,何をどう教えているか 文理複合型情報系組織におけるプログラミング教育の実践例
- 最大次数ΔのC_4フリーグラフの(2Δ-4)彩色数を数え上げるためのマルコフ連鎖モンテカルロ法
- 正六角盤面上のあるペンタヘックスに対するアチーブメントゲームの先手必勝法
- 正六角盤面上のあるペンタヘックスに対するアチーブメントゲームの先手必勝法
- 二次曲線間の交点の二次元複素空間上の可視化ソフトウェア
- 正六角盤面上のポリオミノアチーブメントにおける先手必勝法
- 置換パズルの創作とプレイが可能なゲームシステムの開発(ARとゲーム,映像表現・芸術科学フォーラム2014)
- ボクの壁 : パントマイムの「見えない壁」認識・表示システム(ポスター(シナリオ・キャラクター・ゲーム),映像表現・芸術科学フォーラム2014)
- 演算奏Add : 加法の筆算可聴化システム