Theory and algorithm of state minimization of linear separation automata 線形分離オートマトンの状態数最小化に関する理論およびアルゴリズム

この論文をさがす

著者

    • 沼井, 裕二 ヌマイ, ユウジ

書誌事項

タイトル

Theory and algorithm of state minimization of linear separation automata

タイトル別名

線形分離オートマトンの状態数最小化に関する理論およびアルゴリズム

著者名

沼井, 裕二

著者別名

ヌマイ, ユウジ

学位授与大学

電気通信大学

取得学位

博士 (理学)

学位授与番号

甲第617号

学位授与年月日

2011-03-24

注記・抄録

博士論文

2010

本学位論文では,実ベクトル系列を受理する有限オートマトンの状態数最小化理論,および最小化アルゴリズムについて論ずる.まず,研究の背景について説明する.有限オートマトンは,計算機科学において最も重要な計算モデルの一つである.このモデルは,内部に有限個の状態を持っており,離散的な入力データ(文字列) を受け取ると,状態遷移関数を元に内部の状態を変化させる.計算機科学の世界では,多くの有限状態機械が有限オートマトンを使って設計されている.また,有限オートマトンは電子デバイスの制御システムなどへの応用もなされている.有限オートマトンはまた,多くの研究者によって様々な観点から拡張されてきた.その中には,実数値を取り扱えるように拡張されたモデルも存在する.各状態に微分方程式を付随させた「ハイブリッドオートマトン」や,時間経過に応じた動作を行う「時間オートマトン」などがそれである.「実数値を扱う有限オートマトン」を考えようとしたとき,扱う入力データを「文字列」から「実ベクトル系列」に拡張すればよい,と考えるのは自然である.実際,各状態にサポートベクターマシンを付随させ,実ベクトル系列を取り扱うようにしたオートマトンを動作認識に適用した研究も存在する.ただしその研究は,モデルの理論的な性質を調べているわけではない.実ベクトル系列を受理する有限オートマトンに関する理論的研究は,管見の範囲では見当たらなかった.計算モデルに関する理論的な研究は,そのモデルの性質を知る上でも,モデルを実問題に応用する上でも重要である.しかし一体,どのような理論的研究が要請されるのか.有限オートマトンの世界においては,いくつかの学習アルゴリズムは,状態数最小化の理論およびアルゴリズムを利用して構築されている.有限オートマトンの状態数最小化理論とは,任意の有限オートマトンに対して,それと受理能力が同じで,かつ大きさ(=状態数) が最小となるようなモデルの特徴付けを行う理論である.有限オートマトンの状態数最小化は,モデルの性質の理解および応用の観点から重要な理論である.実ベクトル系列を受理する有限オートマトンにおいても同様に,状態数最小化の理論およびアルゴリズムを打ち立てることが重要であると考えられる.こうした背景のもと,本論文では,実ベクトル系列を受理する有限オートマトンの状態数最小化理論の構築,および最小化アルゴリズムの提案のそれぞれを行う.我々の将来的な目標は,今回我々が取り扱うオートマトンモデルを計算機上に実装し,実問題に適用することにある.ここで留意すべきは,計算機はふつう有限の表現のみを扱うので,実数値を扱う問題も計算機上では有限の表現に近似されることである.問題の表現が有限ならば,もともとの有限オートマトンによってモデル化できる.しかしこのようなモデル化は,複雑過ぎて実用的ではない.その点,我々の扱うモデルは,実数値の関わる問題をコンパクトに,かつ近似的に扱うことが可能である.本論文で取り扱う,実ベクトル系列を受理する有限オートマトンをここでは「線形分離オートマトン(Linear Separation Automaton: LSA)」と呼ぶことにする.LSA の各状態には重みと閾値系列が付随する.この二つによって,入力の各時点において,ある状態からの遷移先状態が決定する.LSA の状態遷移は,パーセプトロンの振舞いと対応する.本論文ではまず,LSA の状態数最小化理論を確立する.最初に,LSAに関するMyhill-Nerode の定理を証明する. これは,LSA の受理言語を特徴付ける定理である.そして,同定理における議論をベースとして,LSA の状態数最小化の理論を確立する.次に,LSA の最小化アルゴリズムを提示し,その正当性を証明する.LSA の最小化アルゴリズムは,状態数の最小化の部分と,閾値系列の最小化の部分とに分けられる.まず,状態数の最小化アルゴリズムを提示し,その正当性を証明する.続いて,状態数を最小化したモデルに対し,各状態の閾値系列の無駄を省いて最小化する手続きを提示する.また,最小化アルゴリズムの時間計算量も同時に示す.最後に,本論文のまとめと今後の課題を提示する.In this thesis, we consider the numerical simulation of electromagnetic waveradiation and propagation problem based on the FDTD method. In order to treat aproblem in an unbounded region by the FDTD method, we adopt the PML techniqueproposed by Berenger in 1994. We show the exact solution for one dimensionalcontinuous problem and investigate the mechanism of artificial reflection caused bydiscretization. Based on these considerations, we propose a new scheme with lowerartificial reflection in the region whose conductivity is constant, and find optimalfunction who give conductivity in the PML region. And we extend a new schemeto two- and three- dimensional problems and verify its validity by some numericalexamples.Next, we consider how to model the antenna and show some difficulties in treatinga circular shaped antenna by FDTD method. We then propose a new method formodeling the antenna as an electrically highly conductive region. Also, we considerthe way of calculating the electric current in an antenna which is important inother method for the analysis of the electromagnetic wave emitted from an antenna.We conclude that our proposal of antenna simulation is effective through severalnumerical simulations.

0アクセス

各種コード

  • NII論文ID(NAID)
    500000547445
  • NII著者ID(NRID)
    • 8000000549537
  • 本文言語コード
    • eng
  • NDL書誌ID
    • 023262930
  • データ提供元
    • 機関リポジトリ
    • NDL-OPAC
ページトップへ