Tarski 算術における冠頭標準形の閉論理式の真偽判定アルゴリズムの提案

  • 柴田 直樹
    大阪大学 大学院基礎工学研究科 情報数理系専攻
  • 岡野 浩三
    大阪大学 大学院基礎工学研究科 情報数理系専攻
  • 東野 輝夫
    大阪大学 大学院基礎工学研究科 情報数理系専攻
  • 谷口 健一
    大阪大学 大学院基礎工学研究科 情報数理系専攻

書誌事項

タイトル別名
  • 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)>である.

収録刊行物

被引用文献 (1)*注記

もっと見る

参考文献 (9)*注記

もっと見る

詳細情報 詳細情報について

  • CRID
    1573950402120580096
  • NII論文ID
    110003191300
  • NII書誌ID
    AN10013152
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ