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

柴田, 直樹; 岡野, 浩三; 東野, 輝夫; 谷口, 健一

このアイテムのアクセス数:47件（2020-12-05 18:52 集計）

このアイテムへのリンクには次のURLをご利用ください:http://hdl.handle.net/11094/27414

閲覧可能ファイル

ファイル	フォーマット	サイズ	閲覧回数	説明
IEICE_J82-D1_6_691	pdf	554 KB	31

論文情報

タイトル	冠頭標準形有理数プレスブルガー文の真偽判定アルゴリズムの提案
別タイトル	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	加算をもつ有理数の理論
	真偽判定アルゴリズム
	組合せ幾何学
	投影

閲覧可能ファイル

論文情報

論文詳細を表示