文献

J-GLOBAL ID：201802215483029763   整理番号：18A2060388

Quirky量子化器:計算木論理の最適モデルと複雑性【JST・京大機械翻訳】

Quirky Quantifiers: Optimal Models and Complexity of Computation Tree Logic

著者 (1件)： Lueck Martin (Institut fuer Theoretische Informatik, Gottfried Wilhelm Leibniz Universitaet, Appelstrasse 4, 30167 Hannover, Germany)
資料名： International Journal of Foundations of Computer Science  (International Journal of Foundations of Computer Science)
巻： 29  号： 1  ページ： 17-61  発行年： 2018年 
JST資料番号： W0409A  ISSN： 0129-0541  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： シンガポール (SGP)  言語： 英語 (EN)

抄録/ポイント： 分岐時間論理CTLの充足可能性問題を,計算複雑性の観点から研究した。各時間演算子フラグメントに対して,タイトな上限と下限を与えた。並列に,最小モデルサイズを最小値の適切な概念で研究した。第三に,平坦なCTL,すなわち非常に低い時間演算子ネスティング深さを持つ公式を調べた。複雑さと最小モデルの観点から,時間的深さ1は低い表現力を持つが,時間的深さ2は完全なCTLと等価であることを示した。Copyright 2018 World Scientific Publishing Company All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 時間論理 ,  計算量 ,  量子化器 ,  *充足可能性問題
準シソーラス用語： 表現力 ,  入れ子構造 ,  *複雑性 , 【Automatic Indexing@JST】

著者キーワード (5件)： CTL ,  時間論理 ,  計算の複雑さ ,  充足可能性 ,  フラグメント

分類 (2件)： 計算理論  (JB02000A) ,  論理代数  (JB03000H)

タイトルに関連する用語 (4件)： 量子化器 ,  論理 ,  モデル ,  複雑性