組織化された系の複雑さを測る方法

• Item type: SIG Technical Reports(1)
• 公開日: 1988-05-23
• タイトル: 組織化された系の複雑さを測る方法
• タイトル / 言語: en
• タイトル: How to Measure the Complexity of Organized Systems Preliminary Report
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: NTT情報通信処理研究所
• 著者所属(英): en
• 著者所属(英): NTT Laboratories Nippon Telegragh and Telephone Corporation
• 著者名: 岡本, 龍明
• 著者名(英): Tatsuaki, Okamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 組織化された系の複雑さを測る一方法を提案する。そのため、情報源に対し、システムコンプレキシティと呼ぶ概念を定義する。また、条件付きシステムコンプレキシティ、及び資源制約システムコンプレキシティを導入する。特に、多項式時間制約条件付きシステムコンプレキシティが、Goldwasserらによって導入された知識コンプレキシティと密接に関連することを示す。さらに、情報源の持つ情報量のみでなく受信者の能力や知識にも依存して決まるような転送情報量を測る一方法を示す。また、複雑度を決定する不完全性並びに実用的測定方法について述べる。最後に、システムコンプレキシティの応用として、計算量理論、通信、及び、生物学的オートマトン理論への応用例を示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The main purpose of this paper is to present a new way to measure the degree of the complexity of organized systems. For this purpose, we define a new notion of complexity, called system complexity. Conditional system complexity and a resource bounded variant of system complexity are also presented. In particular, we show that the polynomial-time bounded conditional system complexity is closely related to the knowledge complexity introduced by Goldwasser et al. In addition, we show a way to measure the amount of transmitted information from sources to destinations and inference processes in the light of system complexity. Incompleteness and practical measurement are also discussed. Finally, a number of applications to computational complexity, communications, and biological automata theory are presented.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1988, 号 36(1988-AL-001), p. 1-8, 発行日 1988-05-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会