プレスブルガー文真偽判定手続きにおける多元連立1次合同式の求解処理の高速化
スポンサーリンク
概要
- 論文の詳細を見る
加算を持つ整数の理論(整数の集合Z上の変数,定数,+,-,=,<,⋀,⋁,∀,∃からなる理論)はプレスブルガー(Presburger)算術と呼ばれ,その上の閉論理式をプレスブルガー文(P文)と呼ぶ.全ての変数が同一の限定記号(∃または∀)で束縛された冠頭形のP文(EPP文)はプログラムや回路の正当性証明などに利用されている.EPP文の真偽判定アルゴリズムでは,掃き出し法に類似した手法を用い,多元連立1次合同式の解をバックトラック探索する処理を多用する.本稿では,この処理を高速化する手法を考案し,いくつかの例題に対して評価を行った.本手法は,解の個数が少ないと予想される変数から解を探索することにより,探索の総試行回数を削減するものである.
- 一般社団法人情報処理学会の論文
- 1996-09-04
著者
-
柴田 直樹
大阪大学大学院基礎工学研究科情報数理系専攻
-
東野 輝夫
大阪大学 大学院情報科学研究科
-
谷口 健一
大阪大学 基礎工学部
-
東野 輝夫
大阪大学大学院情報科学研究科|独立行政法人科学技術振興機構 Crest
-
柴田 直樹
大阪大学 大学院基礎工学研究科 情報数理系専攻
-
森岡 澄夫
大阪大学 大学院基礎工学研究科 情報数理系専攻
-
森岡 澄夫
大阪大学大学院基礎工学研究科情報数理系専攻:(現)日本アイ・ビー・エム株式会社
関連論文
- 2-III-19 B_補酵素関与エタノールアミンアンモニアリアーゼの立体構造と変異導入に基づく触媒機構の解析(一般演題,日本ビタミン学会第62回大会発表要旨)
- 移動センサノードを用いたデータ収集型WSNでのk重被覆時間の最大化手法
- 指向性アンテナおよび車車間通信を用いた歩行者位置追跡手法とその評価(セッション2)
- 12.B_補酵素関与エタノールアミンアンモニアリアーゼの性質とタンパク質工学的改変および結晶構造解析(第415回研究協議会研究発表要旨,ビタミンB研究委員会)
- 車車間通信による交差点鳥瞰映像ストリーミング手法の提案(セッション2)
- 各車両の予定経路情報を利用した車車間通信による情報取得手法の提案(セッション1)
- アプリケーション層マルチキャストミドルウェアの実装とPlanetLab上での評価(セッション4 : オーバレイネットワーク)
- 被災地におけるDTNに基づいた情報収集・共有方式の提案(セッション1-C:マルチメディアシステム)
- 2-II-32 エタノールアミンアンモニアリアーゼのタンパク質工学的改変と結晶構造解析および変異導入(一般研究発表,日本ビタミン学会第61回大会研究発表要旨)
- NGNを活用したセキュア通信提供サービスの提案
- 携帯電話端末への低コスト動画広告配信を目的としたWiFi併用協調ダウンロード方式
- 都市や観光地における混雑状況を考慮した多数ユーザ同時巡回スケジューリング手法
- 通信プロトコルのエラーリカバリ性自動検証の一方式
- アプリケーション層マルチキャストミドルウェアの実装とPlanetLab上での評価(セッション4 : オーバレイネットワーク)
- アプリケーション層マルチキャストミドルウェアの実装とPlanetLab上での評価(セッション4 : オーバレイネットワーク)
- 無線センサネットワーク長寿命化のためのノード集合の分割に基づくスリープスケジューリング手法
- 無線センサネットワーク長寿命化のためのノード集合の分割に基づくスリープスケジューリング手法
- 天気変化を考慮した観光スケジュール群の探索アルゴリズム
- 利用者の状況に応じて画面レイアウトが変更可能な遠隔教育支援システムの提案
- 遷移条件が状態訪問回数に依存する有限状態機械対からなる通信系の生存性検証
- 都市街路における排気ガス量の削減を目的とする車車間通信を想定したリアルタイム信号制御手法の提案
- 凹多面体併合を用いた有理数プレスブルガー文真偽判定アルゴリズムの実装と形式的設計検証への適用
- 有理数プレスブルガー文真偽判定のための多面体分割を用いたアルゴリズムとその実装
- 多面体分割を用いた有理数プレスブルガー文真偽判定アルゴリズムとその実装
- 1G-6 有理数プレスブルガー文真偽判定のための多面体分割を用いたアルゴリズムとその実装
- 冠頭標準形有理数プレスブルガー文の真偽判定アルゴリズムの提案
- 組合わせ幾何を用いた有理数プレスブルガー文真偽判定アルゴリズムにおける投影操作の高速化
- Tarski算術における冠頭標準形の閉論理式の真偽判定アルゴリズムの提案
- 時間ペトリネットモデルで記述されたサービス仕様からのプロトコル仕様の一合成法
- 拡張有限状態機械とペトリネットを表示編集できるGUIツールの作成と応用例
- 動作実行時刻に制約のある分散システムの全体仕様から各ノードの動作記述の自動導出
- 正則な項書換え系のマルチプロセッサ上での一実現法
- レジスタ付き時間ペトリネットで記述された分散システムの時間制約付き全体仕様からその時間制約を満たす各ノードの動作記述の自動導出(並列・分散)
- モバイルアンカノードを用いた低コストな水中センサノードの位置推定法
- 移動センサノードを用いたデータ収集型WSNでのk重被覆時間の最大化手法
- 水面を移動可能なアンカーノードを用いた水中センサネットワークのノード位置推定手法の提案
- 天気変化を考慮した観光スケジュール群の探索アルゴリズム
- ネットワークフローを分散制御するプログラム群の一合成法
- リクエストに応じた交差点映像配信を目的とした車車間通信プロトコルの提案と評価
- メッシュ型物理トポロジのマルチホップWDMネットワークでの階層型コーダルリングネットワーク構築法の検討(次世代ネットワーク,SIP・プレゼンス,一般)
- VANET における車両の経路情報を利用した情報伝播プロトコルの提案と評価
- 負傷者の状態をリアルタイムに監視する電子トリアージ・タッグの評価
- 負傷者の状態をリアルタイムに監視する電子トリアージ・タッグの評価
- 負傷者の状態をリアルタイムに監視する電子トリアージ・タッグの評価
- すべての変数が存在記号で束縛された冠頭標準形プレスブルガー文の真偽判定の高速化手法
- プレスブルガー文真偽判定手続きを用いた算術演算回路の正しさの証明
- プレスブルガー文真僞判定手続きを用いた算術演算回路の正しさの証明
- プレスブルガー文真偽判定手続きにおける多元連立1次合同式の求解処理の高速化
- アプリケーション層マルチキャストミドルウェアにおける携帯端末への映像配信機構の実装
- 分散協調型無線センサノード群の実行コード自動生成
- 分散協調型無線センサノード群の実行コード自動生成
- 確率事象駆動型モデルを利用した無線ネットワークシミュレーション高速化手法の提案
- 確率事象駆動型モデルを利用した無線ネットワークシミュレーション高速化手法の提案
- 確率事象駆動型モデルを利用した無線ネットワークシミュレーション高速化手法の提案
- センサネットワークアプリケーションの実装支援APIの実装と評価
- センサネットワークアプリケーションの実装支援APIの実装と評価
- センサネットワークアプリケーションの実装支援APIの実装と評価
- 代数的仕様の作成・検証・実現支援システムにおける公理解析部の生成
- 一つのEFSMの複数EFSMによる実現の正しさの一証明法
- ノードの移動フローを考慮したMANET上での情報共有方式とその評価(セッション8:データマネージメント)
- ノードの移動フローを考慮したMANET上での情報共有方式とその評価(セッション8:データマネージメント)
- 交差点鳥瞰映像の協調撮影と共有を目的とした車車間通信プロトコル
- 3D仮想空間を用いた情報家電のためのリモコンフレームワーク
- 遅延制約のもとで安定性の高いオーバレイマルチキャスト木を構築する分散型プロトコルの提案
- プログラムの処理速度調整に基づいたデータセンタ向け省電力タスクスケジューリング法
- 過去に観測された品質からのオーバレイリンク品質の推定手法
- 過去に観測された品質からのオーバレイリンク品質の推定手法
- 出庫予測に基づき入店所要時間を最小化する駐車場ナビゲーションの提案
- ユーザのアクティビティと体重変化履歴に基づいた継続性の高い健康支援手法の提案
- ユーザのアクティビティと体重変化履歴に基づいた継続性の高い健康支援手法の提案
- 利己的なエンドノード間でマルチキャストを実現するためのインセンティブ配分法(セッション4 : オーバレイネットワーク)
- 利己的なエンドノード間でマルチキャストを実現するためのインセンティブ配分法(セッション4 : オーバレイネットワーク)
- 利己的なエンドノード間でマルチキャストを実現するためのインセンティブ配分法(セッション4 : オーバレイネットワーク)
- トポロジの多重化によりトラヒック分散を実現した階層型論理トポロジの構成法とそのルーティングアルゴリズム(映像通信,コンテンツ配信ネットワーク,マルチキャスト,一般)
- コンポーネント連携によるサービスをオーバレイネットワーク上で実現するためのサービス設計技法の提案
- アプリケーションレベルマルチキャストEmmaの性能向上に関する検討
- カラーペトリネットを用いた分散協調システムの設計とSOAPを用いた一実装法の提案
- 駐車待ち所要時間を最小化する駐車場ナビゲーションの提案
- 駐車待ち所要時間を最小化する駐車場ナビゲーションの提案
- 駐車待ち所要時間を最小化する駐車場ナビゲーションの提案
- 過去に観測された品質からのオーバレイリンク品質の推定手法
- 13.B_補酵素関与エタノールアミンアンモニアリアーゼの精密触媒機構と立体化学経路(第423回研究協議会研究発表要旨,ビタミンB研究委員会)
- SumiTag :あまり目立たないARマーカーとGPGPUを利用した読み取り方法
- 過去に観測された品質からのオーバレイリンク品質の推定手法(モバイルコンピューティング,モバイルアプリケーション,ユビキタス通信,モバイルマルチメディア通信及び一般)
- 3Da01 アミド化合物の酵素合成 : 高効率触媒の形成要件(酵素学・酵素工学,一般講演)
- 3Da12 6-アミノヘキサン酸環状二量体加水分解酵素(NylA)の基質結合部位の解析(酵素学・酵素工学,一般講演)
- 2Dp14 ナイロンオリゴマー分解酵素(NylC)の高度耐熱化(酵素学・酵素工学,一般講演)
- 2Dp13 ナイロンオリゴマー加水分解酵素(NylC)の自己分断機構(酵素学・酵素工学,一般講演)
- 穿孔部封鎖処置における歯科用コーンビームCTとマイクロスコープの応用
- ターボブースト・ハイパースレッディングを考慮したマルチコアプロセッサ向けタスクスケジューリング
- 歯内療法領域における歯科用CTを用いた画像診断に関するクリニカルパスの構築
- 12.B_補酵素関与ジオールデヒドラターゼのグリセロールによる不活性化の機構と不活性化抵抗性酵素の再設計(第427回研究協議会研究発表要旨,ビタミンB研究委員会)
- 照明点灯パターンの切り替えによる高精度な屋内位置推定法とその評価(モバイルアドホックネットワーク,モバイル時代を支える次世代無線技術,フィールドセンシング及び一般)
- 4Ca02 ナイロン加水分解酵素(NylC)の耐熱化機構(酵素学,酵素工学/タンパク質工学,一般講演)
- 運転者に対する交通安全支援のための指向性アンテナおよび車車間通信を用いた歩行者の位置推定手法
- 4Ca01 ナイロン加水分解酵素(NylC)前駆体の自己分断に及ぼすアミノ酸置換効果(酵素学,酵素工学/タンパク質工学,一般講演)
- 移動アンカノードを用いた三辺測量による水中センサノードの低コスト位置推定手法
- 2P-045 高解像度X線結晶構造解析を基盤としたナイロン加水分解酵素(NylC)の耐熱化機構の解明(酵素学,酵素工学,一般講演)
- 2P-044 分子動力学シミュレーションによるナイロン加水分解酵素(NylC)の自己分断機構の解析(酵素学,酵素工学,一般講演)
- BalloonNet:無線ネットワークノードを用いた建物包囲型三次元配置手法