冠頭標準形有理数プレスブルガー文の真偽判定アルゴリズムの提案

柴田, 直樹; 岡野, 浩三; 東野, 輝夫 他

電子情報通信学会論文誌D, 1999, J82-D1(6), 691-700

アクセス数:688件（2025-07-06 09:57 集計）

固定URL: https://hdl.handle.net/11094/27414

閲覧可能ファイル 

ファイル フォーマット 利用条件 サイズ 閲覧回数 利用開始日 説明 information
IEICE_J82-D1_6_691 pdf なし 554 KB 75 2014.04.11  

論文情報

ファイル出力 EndNote Basic出力 Mendeley出力

タイトル
冠頭標準形有理数プレスブルガー文の真偽判定アルゴリズムの提案
A Decision Algorithm for Prenex Normal Form Rational Presburger Sentences
カントウ　ヒョウジュンケイ　ユウリスウ　プレスブルガーブン　ノ　シンギ　ハンテイ　アルゴリズム　ノ　テイアン
著者
NRID
1000040335477 1000040335477
著者名
柴田, 直樹 ; シバタ, ナオキ ; Shibata, Naoki
NRID
1000070252632 1000070252632
著者名
岡野, 浩三 ; オカノ, コウゾウ ; Okano, Kozo
NRID
1000080173144 1000080173144
researchmap permalink
teruo.higashino teruo.higashino
Scopus Author ID
7005648670 7005648670
著者名
東野, 輝夫 ; ヒガシノ, テルオ ; Higashino, Teruo
NRID
1000000029513 1000000029513
著者名
谷口, 健一 ; タニグチ, ケンイチ ; Taniguchi, Kenichi
キーワード等
加算をもつ有理数の理論
真偽判定アルゴリズム
組合せ幾何学
投影
抄録
本論文では，加算をもつ有理数の理論（有理数変数，有理数定数，+,-,=,<, ∧, ∨, ∀, ∃からなる理論）の冠頭標準形閉論理式に対する，時間計算量が r ・ α^<βd>n^＜γ d (b+1)＾a >（α,β,γ は定数，n は入力の式に含まれる不等式の個数，d は変数の個数，a は限定子交替数，b は同じ限定子が続く最大の個数，r は入力の式の各係数と定数の分母，分子のビット数）の計算幾何学の手法を利用した真偽判定アルゴリズムを提案する．従来知られていた真偽判定アルゴリズムの最良の時間計算量は r ・ 5^<εd>n^<ζ d (2b+1)^a>（ε,ζ は定数）である．
出版者
電子情報通信学会
The Institute of Electronics, Information and Communication Engineers
デンシ　ジョウホウ　ツウシン　ガッカイ
収録物名
電子情報通信学会論文誌D
巻(号)
J82-D1(6)
ページ
691-700
刊行年月
1999-06-25
言語
日本語
ハンドルURL
https://hdl.handle.net/11094/27414
PISSN
09151915
NCID
AA11341020
関連情報 (references)
URI
http://search.ieice.org/
アクセス権
open access
権利情報
Copyright © 1999 IEICE
出版タイプ
Version of Record
カテゴリ
学術雑誌論文 Journal Article