複雑系の計算には、計算モデルが検証されているかは
時間値による状態爆発を回避した時間的双模倣等価性検証法(計算モデルと計算の複雑さに関する研究)
... 大阪大学基礎工学部情報工学科 $\mathrm{E}_{-}\mathrm{m}\mathrm{a}\mathrm{i}1:$ { $\mathrm{n}\mathrm{a}\mathrm{k}\mathrm{a}\mathrm{t}\mathrm{a}$ , higashino, ...
7
等号を含む第一階時相論理のサブクラスとその恒真性判定問題(計算モデルと計算の複雑さに関する研究)
... 階述語論理のサブクラスを用いてマイクロプロセッサの検証を行って いる [3]。問題が決定可能なので、完全な自動化が可能になるという特長がある。 しかし、 この ...
7
正則パターン言語和の包含に関する強コンパクト性(計算モデルと計算の複雑さに関する研究)
... (DFA) に線形時間で変換できる (Shinohara 1982). さらに, 任意の正則パターン言語は, Kleene $\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}*$ を用いずに $w_{0}\overline{\epsilon}w1\ldots w_{n}-1i\overline{\epsilon}w_{n_{i}}$ ...
4
可変マージ関数の否定数限定複雑さ (計算モデルとアルゴリズム)
... $\mathrm{R}\mathrm{a}\mathrm{z}\mathrm{b}\mathrm{o}\mathrm{r}\mathrm{o}\mathrm{v}[\mathrm{R}\mathrm{a}\mathrm{z}]$ は , $\mathrm{N}\mathrm{P}$ に属するクリーク関数を否定ゲートを 用いない単調論理回路で計算するには, ...
6
ある制限されたチャイニーズ・ポストマン問題の計算量(計算モデルと計算の複雑さに関する研究)
... 計算量にも興味を持っている. 5 参考文献 1) Aho, A.V., Hopcroft, J.E., and Ullman, $\mathrm{J}.\mathrm{D}.$ : The Design and Analysis of Computer Algo- rithms, ...
7
2次元可逆セル・オートマトンにおける一斉射撃問題(計算モデルと計算の複雑さに関する研究)
... [5] はいくつかの 図形のクラスに対するより高速な解を示した . われわれは , この – 斉射撃問題を可逆セルオート マトン上で実現することを試みた ...– の状態 になるという意味での–斉射撃解は存在せず, ...
5
2層プラナー(計画器)の提案:自然言語理解のために(計算モデルと計算の複雑さに関する研究)
... Goal の達成には既成の Prolog プログラム $\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}_{-}\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{S}\mathrm{t}_{-}\mathrm{S}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{h}$ ...
7
unrestricted LR 文法及び unrestricted LR 構文解析法の提案(計算モデルと計算の複雑さに関する研究)
... とを燐 $\frac{\alpha_{1}}{*r}q_{j}$ によって表し, 集合 $U,$ $V$ の長 さ $k$ の連接集合を $U\oplus_{k}V$ で表す . $LI\mathrm{t}_{k([\alpha}^{\nearrow}1arrow\alpha_{2}\cdot]$ , $Si)=$ ...
7
進化生物学における離散最適化問題の解法について : 祖先形質復元問題に対する線形時間アルゴリズム(計算モデルと計算の複雑さに関する研究)
... The second pass of the previous algorithm in [4] for Problem 4 is not a little complicated and it complexity is $\mathrm{O}(n^{2})$ for the number $n$ of nodes in a given $\mathrm{e}1$ -[r] ...
10
二分決定グラフに基づく計算複雑さに関する未解決問題について(計算量理論の諸相 : その基礎的研究)
... 論理関数処理のためのデータ構造とし て、 論理回路設計支援システムや組合せ問題の求解などの分野で多く用いられている。 BDD を – 種の計算モデルとして扱い、その表現能力を計算複雑さの理論に基づいて明 ...
7
有限曖昧経営オートマトンの等価性判定問題の可解性(計算モデルと計算の複雑さに関する研究)
... $F>$ は、 有限オートマトンである。語 $w\in\Sigma^{*}$ は \mbox{\boldmath$\delta$}(S, $w$ ) $\in$ F であるとき , 有 限オートマトン $A$ によって受理されるという ...$e$ は $Q_{\mathrm{X}}\Sigma_{\mathrm{X}}Q$ から ...
7
複数プロセス故障を許した耐故障分散相互排除アルゴリズム(計算モデルと計算の複雑さに関する研究)
... 更新テーブル update 切は, プロセス j が故障した場合 コーラム中のプロセス $j$ を $update[j]$ で置き換えること を示す . 故障プロセス $j$ を検出したことを示すメッセー ジ DOwn( のを受信したプロセスは , まず次に示す手続 きによりこの更新テーブルを更新する. ...
5
NP完全なブール関数に対する多項式時間スライス関数について(計算モデルと計算の複雑さに関する研究)
... TONIAN CIRCUIT, BANDWIDTH などのグラフの性質に関する $\mathrm{N}\mathrm{P}$ 完全関数のスライス関数で、多 項式サイズ回路で計算できるものをいくつか示す。 これらの結果を得るために、 Tur\’an グラフなどの特 定のグラフの認識問題を考察する。 1 ...
7
PRAMおよび対数時間一様な論理回路族に基づく計算量の階層(計算モデルと計算の複雑さに関する研究)
... of problems solvable by constant depth, polynomial- size, unbounded fan-in Boolean circuits in which any “MOD $(k)- \mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e},’)k>1$ , may be used.. One[r] ...
7
近似解をも考慮に入れた多項式時間変換(計算モデルと計算の複雑さに関する研究)
... が $0$ になることになる. 一般に, 頂点 $i$ を $j$ 回重複して選んだら, $0$ となる節は , $C_{2}$ 個になる . これ を全ての $0\leq i\leq n-1$ に関して足し合わせた個数がステップ 1 で作られた節のうち $0$ となる数であ る . ...
6
Tutte多項式とJones多項式の計算(計算モデルと計算の複雑さに関する研究)
... Tutte 多項式はグラフ理論の分野において基本的かつ重要な不変量であり、結び目の分野に おける交代絡み目の Jones 多項式とも関係があることが知られている。本稿では、最近提示した Tutte 多項式を計算する新しいアルゴリズムを – ...
7
スキーママッチングにおける計算の複雑さ (計算モデルとアルゴリズム)
... が得られるとき, $\Phi$ は $\Psi$ と $\alpha$ 同値であるといい, $\Phi=_{\alpha}\Psi$ と表す. 3 スキーママッチング スキーマ表現と項表現を合わせて単に表 現 (expression) という 表現 $E=\{\langle\Phi_{i\backslash }.\varphi_{i}\rangle$ $|$ ...
6
多段階木変換機について(計算モデルと計算の複雑さに関する研究)
... $Q$ の元を変換状態という. $\Sigma$ は階層化アルファベット , $F\subseteq P$ は最終状態の集合 , $q0\in Q$ は初期状態である ...$\rho=\{\rho_{\sigma}|\sigma\in\Sigma\}$ はボトムアップ変換のものと同様である. ...
7
推論加群系と自動証明への応用(計算モデルと計算の複雑さに関する研究)
... $\frac{t_{n}}{X_{n}}\rangle$ は表現 中の変数記号のうち, $X_{i}\in\{\hat{X}\}$ は項 $t_{i}\in\hat{t}$ で置き換え るが, $\hat{X}$ 以外の変数記号は to で置き換える ...1 は , ...
7
積グラフの独立な全域木(計算モデルと計算の複雑さに関する研究)
... $Q_{\mathit{7}l}$ は $Q_{n-1}$ ) $\langle I\iota_{2}^{-}=$ $Q_{n-2^{\mathrm{X}}}I_{1^{\vee}}2\cross I\iota_{2}’=\cdots=I\iota_{22}’\cross I1^{-}\cross\cdots\cross Ii_{2}$ で, 一般 $ll$ 次元ハイパーキューブ $Q_{n}^{t}$ は ...
7