| 題名 | 非決定性回路族における深さと非決定性ゲート数の関係 |
| 著者 | *小野 優介 (広島大学大学院工学研究科情報工学専攻), 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学大学院工学研究科) |
| Page | pp. 369 - 370 |
| Keyword | 計算複雑性, 複雑性クラス, 論理回路族 |
| Abstract | 論理回路族による複雑性クラスNCを基にして過去に提案されたクラスNNC(f(n))を題材としてその包含関係を探究する。クラスNNC(f(n))は、非決定性ゲート数f(n)を小さくすることでNCと等しくなり、大きくすることでクラスNPに等しくなるという性質を持つ他、NCが回路の深さによって階層分けされることと同様にNNC(f(n))も回路の深さによって分けられる。本稿では深さと非決定性ゲート数の大小による包含関係を示す。 |
| 題名 | 大学時間割作成問題の計算複雑さ |
| 著者 | *高田 健太郎 (広島大学大学院工学研究科情報工学専攻), 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学大学院工学研究科) |
| Page | pp. 371 - 372 |
| Keyword | 大学, 時間割, 最大流, マッチング, 多項式 |
| 題名 | 直交テラインの警備問題 |
| 著者 | *岸 純一, 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学大学院工学研究科情報工学専攻) |
| Page | pp. 373 - 374 |
| Keyword | 警備問題, 計算幾何学, テライン, アルゴリズム, 必要十分条件 |
| 題名 | 書換規則の分割による一意解析可能アレイ文法の簡約化手法の提案とその実装 |
| 著者 | *野口 明宏, 今井 克暢, 森田 憲一, 岩本 宙造 (広島大学大学院工学研究科) |
| Page | pp. 375 - 376 |
| Keyword | UPAG, 書換規則, 分割, アルゴリズム |
| Abstract | コンピュータ上での画像処理手法の１つとして, アレイ文法の研究が数多くなされてきた.アレイ文法とは, 形式文法を２次元へ拡張したものである.今回は効率よく解析可能な文法である, 一意解析可能アレイ文法に着目する.しかしUPAGには標準形がなく, パターンサイズが大きな規則を含む場合が多くなるため, その設計はヒューリスティックな試行錯誤によらざるを得ない.そこで本研究では, 与えられたUPAGの書換規則をより小さなものに書き換えることを目標とする. そのアプローチとして, ある書換規則がUPAG条件を満たすように分割するアルゴリズムを提案するとともに, そのプログラムを作成する. |
| 題名 | 時間ペトリネットに基づくシグナル伝達経路モデルの発火頻度条件式導出アルゴリズムの提案 |
| 著者 | *三輪 良雅 (山口大学大学院理工学研究科), 樋岡 幹司 (バブ日立ソフト株式会社), 葛 崎偉 (山口大学教育学部), 松野 浩嗣 (山口大学大学院理工学研究科) |
| Page | pp. 377 - 378 |
| Keyword | ペトリネット, シグナル伝達経路, モデル化, アルゴリズム, シミュレーション |
| Abstract | ペトリネットは様々な並行システムのモデル化において有用であることが示されているシステム記述法であり，近年は，生命パスウェイのモデル化手法としても応用されている．シグナル伝達経路は，生体の活動が適切に行われるように細胞のふるまいを統一する情報伝達機構である．現在，李らにより，離散ペトリネットを使いシグナル伝達経路をモデル化する手法と時間ペトリネットを用いてペトリネットの構造からトランジションの発火頻度を決定する手法が提案されている．本稿では，李らの手法の問題点を解決した時間ペトリネットにおいて新たな発火頻度を決定する条件式を導出し，ペトリネットモデルに適用できるアルゴリズムを提案する． |
| 題名 | Acyclic自由選択ワークフローネットに対する直列化可能性判定の一考察 |
| 著者 | 山口 真悟 (山口大学大学院理工学研究科), *浜野 慎司 (山口大学工学部), 黒田 祐樹, 田中 稔 (山口大学大学院理工学研究科) |
| Page | p. 379 |
| Keyword | ペトリネット, ワークフロー, 直列化可能性, リファクタリング, WFネット |
| Abstract | ワークフローネット（以下WFネット）はワークフローをモデル化するためのペトリネットである．実用的なワークフローは自由選択（以下FC）WFネットでモデル化できることが知られている．複数の事例を伴うWFネットはその振る舞いを事例ごとに分割して解析できることが望まれる．その条件の一つに直列化可能性がある．しかしFCWFネットに対する直列化可能性の判定は検討されていない．本稿では，そのクラスに対する直列化可能性の判定法を提案する． |
| 題名 | LINとSSLを認識する感知型逆ワトソン・クリック有限オートマトン |
| 著者 | *村上 和樹 (島根大学大学 院総合理工学研究科), 坂本 典子 (島根大学大学院 総合理工学研究科), 會澤 邦夫 (島根大学 総合理工学部) |
| Page | p. 380 |
| Keyword | DNA計算, ワトソン・クリックオートマトン, スティッカーシステム, 計算モデル |
| Abstract | DNA計算はAdelmanの実験をきっかけに，極小サイズかつ高速なコンピュータを実現する為の方法の1つとして考えられた．DNA計算における計算モデルの1つであるワトソン・クリックオートマトンはG. Păunらによって導入され，これまで種々のタイプのワトソン・クリックオートマトンが研究されてきた．現在，線形言語のクラス及び単純スティッカーシステムの言語クラス（SSL）とこれらのオートマトンとの関係は未知である．そこで，本研究ではLIN及びSSLを認識する感知型逆ワトソン・クリック有限オートマトン（以下SRWKFA）を提案し，SRWKFAが認識する言語クラスASRWKに対してLIN⊆ASRWK， SSL⊆ASRWKが成り立つことを示す． |