ある種のNLCグラフ文法によるグラフの集合の学習
スポンサーリンク
概要
- 論文の詳細を見る
本稿では、あるグラフの集合族が多項式時間で学習可能であることを示す。RNLC(regular node label controlled)グラフ文法Gが制限つきRNLCグラフ文法であるとは、Gが次の性質を持つときをいう:(1)Gは対称性を持つ。すなわち、(a,b)∈connならば(b,a)∈connである、ここで、connは接続関係である。(2)任意の非終端ラベルAと任意の終端ラベルaに対して、(a,A)∈connである。(3)開始グラフは、単一の頂点からなる。定理tを固定された非負整数とする。制限つきRNLCグラフ文法で、そのParikh写像が高々t周期となる文法で記述されるグラフの集合族は、制限つきsubsetqueryと制限つきsupersetqueryから多項式時間限定で同定できる。
- 社団法人電子情報通信学会の論文
- 1995-07-27
著者
関連論文
- 西野哲郎 (著), 量子コンピュータ入門 東京電機大学出版局, 146p, 2600円 (本体のみ・税別) ISBN4-501-52650-5 C3055
- k-ツリーを用いたP^k_nの新しい特徴付け
- NP完全なブール関数に対する多項式時間スライス関数について(計算モデルと計算の複雑さに関する研究)
- restricted RNLC グラフ言語の学習(計算量理論の諸相 : その基礎的研究)
- ある種のNLCグラフ文法によるグラフの集合の学習
- 量子情報理論とその応用論文小特集の発行にあたって(量子情報理論とその応用)
- Some Results for Cluster Traveling Salesperson Problem
- ある拡張された巡回セールスマン問題について
- The algorithmic aspect of "probabilistic method independent number theorem"
- ある種のグラフ問題に対するsearchとdecisionのギャップについて