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

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

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

Number of Access:749（2025-08-31 18:55 Counts）

Identifier to cite or link to this item: https://hdl.handle.net/11094/27414

Link to primary information 

File Format Terms of use Size Views Date.Available Description information
IEICE_J82-D1_6_691 pdf None 554 KB 86 2014.04.11  

Item Information

Output File Export EndNote Basic Export Mendeley

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