書誌事項
- タイトル別名
-
- A decision algorithm for prenex normal form sentence in Tarski arithmetic
この論文をさがす
説明
加算を持つ有理数 (あるいは実数) の理論 (有理数変数, 有理数定数, +, -, =, <, ∧, ∨からなる理論) はTarski算術と呼ばれる. 本稿では, Tarski算術の冠頭標準形閉論理式 (ここではPRP文と呼ぶ) に対する, 計算幾何学の手法を利用した時間計算量が (n+d)^<O(d)>^<a+1> (nは入力のPRP文に含まれる不等式の個数, dは変数の個数, αは限定子交替数) のPRP文真偽判定アルゴリズムを提案する. 従来知られていた真偽判定アルゴリズムの時間計算量はl^<O(d)>^<4a-2> (lは入力のPRP文の長さ), および2^2^<O(1)>である.
収録刊行物
-
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
-
電子情報通信学会技術研究報告. COMP, コンピュテーション 97 (356), 17-24, 1997-10-31
一般社団法人電子情報通信学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1573950402120580096
-
- NII論文ID
- 110003191300
-
- NII書誌ID
- AN10013152
-
- 本文言語コード
- ja
-
- データソース種別
-
- CiNii Articles