雑誌ブラウズ
雑誌 全て
大阪大学 刊行物
ランキング
アクセスランキング
ダウンロードランキング
博士論文のみをさがす
リポジトリ登録支援システム
附属図書館
このアイテムのアクセス数:
82
件
(
2022-05-18
02:58 集計
)
このアイテムへのリンクには次のURLをご利用ください:http://hdl.handle.net/11094/27414
閲覧可能ファイル
ファイル
フォーマット
サイズ
閲覧回数
説明
IEICE_J82-D1_6_691
pdf
554 KB
41
論文情報
タイトル
冠頭標準形有理数プレスブルガー文の真偽判定アルゴリズムの提案
別タイトル
A Decision Algorithm for Prenex Normal Form Rational Presburger Sentences
タイトル (ヨミ)
カントウ ヒョウジュンケイ ユウリスウ プレスブルガーブン ノ シンギ ハンテイ アルゴリズム ノ テイアン
著者
柴田, 直樹
柴田, 直樹
岡野, 浩三
岡野, 浩三
東野, 輝夫
東野, 輝夫
谷口, 健一
谷口, 健一
著者の別表記
Shibata, Naoki
Okano, Kozo
Higashino, Teruo
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
ISSN
09151915
NCID
AA11341020
URL
http://hdl.handle.net/11094/27414
関連情報 (references)
http://search.ieice.org/
権利情報
Copyright © 1999 IEICE
言語
日本語
カテゴリ
学術雑誌論文 Journal Article
論文詳細を表示
著者版フラグ
publisher
NII資源タイプ
学術雑誌論文
ローカル資源タイプ
学術雑誌論文
dcmi資源タイプ
text
DCTERMS.bibliographicCitation
電子情報通信学会論文誌D.J82-D1(6) P.691-P.700
DC.title
冠頭標準形有理数プレスブルガー文の真偽判定アルゴリズムの提案
DCTERMS.alternative
A Decision Algorithm for Prenex Normal Form Rational Presburger Sentences
DC.creator
柴田, 直樹
岡野, 浩三
東野, 輝夫
谷口, 健一
DC.creator
Shibata, Naoki
Okano, Kozo
Higashino, Teruo
Taniguchi, Kenichi
DC.publisher
電子情報通信学会
DC.language" scheme="DCTERMS.RFC1766
日本語
DCTERMS.issued" scheme="DCTERMS.W3CDTF
1999-06-25
DC.identifier" scheme="DCTERMS.URI
http://hdl.handle.net/11094/27414
DC.subject
加算をもつ有理数の理論
真偽判定アルゴリズム
組合せ幾何学
投影
DCTERMS.abstract
本論文では,加算をもつ有理数の理論(有理数変数,有理数定数,+,-,=,<, ∧, ∨, ∀, ∃からなる理論)の冠頭標準形閉論理式に対する,時間計算量が r ・ α^<βd>n^<γ d (b+1)^a >(α,β,γ は定数,n は入力の式に含まれる不等式の個数,d は変数の個数,a は限定子交替数,b は同じ限定子が続く最大の個数,r は入力の式の各係数と定数の分母,分子のビット数)の計算幾何学の手法を利用した真偽判定アルゴリズムを提案する.従来知られていた真偽判定アルゴリズムの最良の時間計算量は r ・ 5^<εd>n^<ζ d (2b+1)^a>(ε,ζ は定数)である.
DC.rights
Copyright © 1999 IEICE
citation_title
冠頭標準形有理数プレスブルガー文の真偽判定アルゴリズムの提案
citation_author
柴田, 直樹
岡野, 浩三
東野, 輝夫
谷口, 健一
citation_publisher
電子情報通信学会
citation_language
日本語
citation_date
1999-06-25
citation_journal_title
電子情報通信学会論文誌D
citation_volume
J82-D1
citation_issue
6
citation_firstpage
691
citation_lastpage
700
citation_issn
09151915
citation_public_url
http://hdl.handle.net/11094/27414
citation_keywords
加算をもつ有理数の理論
真偽判定アルゴリズム
組合せ幾何学
投影