Tarski算術における冠頭標準形の閉論理式の真偽判定アルゴリズムの提案
スポンサーリンク
概要
- 論文の詳細を見る
加算を持つ有理数 (あるいは実数) の理論 (有理数変数, 有理数定数, +, -, =, <, ∧, ∨からなる理論) はTarski算術と呼ばれる. 本稿では, Tarski算術の冠頭標準形閉論理式 (ここではPRP文と呼ぶ) に対する, 計算幾何学の手法を利用した時間計算量が (n+d)^<O(d)>^<a+1> (nは入力のPRP文に含まれる不等式の個数, dは変数の個数, αは限定子交替数) のPRP文真偽判定アルゴリズムを提案する. 従来知られていた真偽判定アルゴリズムの時間計算量はl^<O(d)>^<4a-2> (lは入力のPRP文の長さ), および2^2^<O(1)>である.
- 1997-10-31
著者
-
東野 輝夫
大阪大学大学院情報科学研究科
-
柴田 直樹
大阪大学大学院基礎工学研究科情報数理系専攻
-
岡野 浩三
大阪大学大学院情報科学研究科
-
谷口 健一
大阪大学大学院情報科学研究科
-
東野 輝夫
大阪大学大学院情報科学研究科|独立行政法人科学技術振興機構 Crest
関連論文
- 災害現場でセンシングされた生体情報を集約する無線センサーネットワークの構成法(モバイルコンピューティング、モバイルアプリケーション、ユビキタス通信、モバイルマルチメディア通信)
- ネットワークオンチップにおける回路面積と配線コストを考慮したチップ内通信構造最適化の一手法(コンピュータシステムの設計・検証及び一般,デザインガイア2007-VLSI設計の新しい大地を考える研究会)
- アドホック通信に基づく行先経路の道路情報取得プロトコルの開発(セッション2,ITS情報処理・一般)
- アドホック通信に基づく行先経路の道路情報取得プロトコルの開発(セッション2)(ITS情報処理・一般)
- 詳細度の異なるモデルを用いた無線シミュレーションの高速化手法の提案(Work in Progress,ワイヤレス環境でのアプリケーション品質,P2P/アドホックネットワーク,画像符号化,ストリーム技術,信頼性,一般)
- 無線メッシュネットワークにおけるWDSクラスタ分割アルゴリズムの改善(無線ネットワーク)
- 災害医療支援ネットワークのための軽傷者用負傷者端末(システム設計,物理設計及び一般)
- 位置情報に基づくTDMプロトコルの提案(セッション1)
- 車車間通信を利用した信号機制御手法の提案
- 車車間通信を用いた危険車両の検出手法の提案(車車間通信技術,次世代社会基盤をもたらす高度交通システムとモバイル通信システム)
- メッセージフェリーと車車間通信を併用した渋滞情報収集システムの情報伝播効率の改善(車車間通信技術,次世代社会基盤をもたらす高度交通システムとモバイル通信システム)
- データ付時間オートマトンの双模倣等価性の記号的検証法
- MANETを用いた災害時における被災者の位置情報収集・追跡システムの提案(交通における計測・一般(電気系3学会ITS合同研究会))
- MANETを用いた災害時における被災者の位置情報収集・追跡システムの提案(交通における計測, 一般(電気系3学会ITS合同研究会))
- 1J-4 センサーネットワークの設計開発を支援するシミュレーション融合型テストベットの検討(情報爆発時代における情報提示・センサネット・P2P,一般セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- 無線メッシュネットワークのアクセスポイント間通信での優先度順リンク動作方式(トラヒックエンジニアリング,一般,トラヒック,NW評価,性能,リソース管理・制御,トラヒックエンジニアリング,NW信頼性・レジリエンシ,一般)
- 先行経路上の道路情報取得用アドホック通信プロトコルの開発(ITS)
- 目的地選択の公平性と指定されたノード密度分布を実現する移動モデルの提案(学生特別セッション,移動通信ワークショップ)
- チップ内ネットワークの性能要求検証および最適化のための一手法(ネットワーク,通信)
- 即時通信を行うハードウェアのサイクル精度動作記述モジュール群に対するモデル検査の一手法(FPGAとその応用及び一般)
- 即時通信を行うハードウェアのサイクル精度動作記述モジュール群に対するモデル検査の一手法
- 部品のコスト・性能を考慮したリアルタイム組込みシステムの一設計法(VLSI設計技術とCAD)
- 外部入力値のみを保持できる整数変数をもつFSMに対する記号モデル検査法(ソフトウェア工学)
- 実時間通信システムに対する高信頼ハードウェア合成手法の提案(VLSIの設計/検証/テスト及び一般論理合成及び高位合成)
- 実時間通信システムに対する高信頼ハードウェア合成手法の提案(VLSIの設計/検証/テスト及び一般 論理合成及び高位合成)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 並行周期EFSM群でモデル化されたQoSルータの高信頼性設計の一手法
- 並行周期EFSMに対するパラメトリックモデル検査手法(LAシンポジウム(計算機科学基礎理論ワークショップ)論文小特集)
- 並行周期EFSMに対するパラメトリックモデル検査およびパラメタ条件簡約高速化の一手法
- 無線センサーネットワークを利用した電子トリアージシステムの実現(モバイル/放送融合アプリケーション,モバイルコンテンツ,モバイル映像配信,一般)
- 無線センサーネットワークを利用した電子トリアージシステムの実現(学生特別セッション,モバイル/放送融合アプリケーション,モバイルコンテンツ,モバイル映像配信,一般)
- 傷病者の自動監視を実現する電子トリアージシステム(モバイル P2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- NGNを活用したセキュア通信提供サービスの提案
- ノード群の相対位置関係に基づく位置推定アルゴリズムの評価手法
- 移動無線端末の位置情報と通信情報を用いた災害現場地図の自動生成
- 断続的に移動する無線端末群の位置推定
- 災害時救急救命支援に向けた電子トリアージシステムの設計開発
- 遭遇端末の位置情報と地理情報を併用した高精度な位置推定手法の提案と評価(ユビキタスネットワーク,ITS,センサーネットワーク,アドホックネットワーク)
- BP-7-5 オーバレイ・エージェントプラットフォームPIAXとその展開(BP-7.プラットフォーム化へ向かうユビキタス・センサネットワーク,パネルセッション,ソサイエティ企画)
- Deformable Templateマッチング法による唇輪郭抽出法の改良と歯科医療応用を目的とした評価(画像処理,画像パターン認識)
- Deformable-Templateマッチング法による唇輪郭抽出法の改良としきい値自動調整アルゴリズムの提案
- 関数合成による唇輪郭抽出法の提案
- Deformable-Templateマッチング法による唇輪郭抽出法の改良と内眼角点を原点とする座標系表現法の提案
- 都市街路における排気ガス量の削減を目的とする車車間通信を想定したリアルタイム信号制御手法の提案
- 計算負荷分散を考慮した近隣端末の分散型移動予測手法の提案
- センサネットワークアプリケーションの実装支援APIの実装と評価
- 確率事象駆動型モデルを利用した無線ネットワークシミュレーション高速化手法の提案
- 確率事象駆動型モデルを利用した無線ネットワークシミュレーション高速化手法の提案
- 確率事象駆動型モデルを利用した無線ネットワークシミュレーション高速化手法の提案
- 確率事象駆動型モデルを利用した無線ネットワークシミュレーション高速化手法の提案
- 先行道路情報取得プロトコルRMDPの設計と評価(ITS)
- 行先道路情報取得プロトコルRMDPの評価と車々間・路車間通信混在環境への適応(セッション7)(テーマ:モバイルコンピューティング,ITS,放送コンピューティング)
- 行先道路情報取得プロトコルRMDPの評価と車々間・路車間通信混在環境への適応(セッション7)(テーマ:モバイルコンピューティング,ITS,放送コンピューティング)
- アドホック通信に基づく行先経路の道路情報取得プロトコルの開発
- チップ内ネットワークの性能要求検証および最適化のための一手法(ネットワーク,通信)
- チップ内ネットワークの性能要求検証および最適化のための一手法(ネットワーク,通信)
- チップ内ネットワークの性能要求検証および最適化のための一手法(ネットワーク,通信)
- 傷病者の自動監視を実現する電子トリアージシステム(モバイル P2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- 災害現場の被災者や救援者の行動記述とそれを用いたネットワークシミュレーション環境の提案
- 負傷者の状態をリアルタイムに監視する電子トリアージ・タッグの評価
- 負傷者の状態をリアルタイムに監視する電子トリアージ・タッグの評価
- 負傷者の状態をリアルタイムに監視する電子トリアージ・タッグの評価
- 負傷者の状態をリアルタイムに監視する電子トリアージ・タッグの評価
- 冠頭標準形有理数プレスブルガー文の真偽判定アルゴリズムの提案
- 複数時間オートマトンによる仕様記述と検証
- 組合わせ幾何を用いた有理数プレスブルガー文真偽判定アルゴリズムにおける投影操作の高速化
- 時間ペトリネットの拡張モデルを用いたプロトコル合成
- Tarski算術における冠頭標準形の閉論理式の真偽判定アルゴリズムの提案
- 耐故障性のための多重化リソースを持つ分散システムの導出法
- GUI制御部の記述と実現の一手法
- 規則右辺に照合外変数を含む条件付き項書換え系における階層合流性のモジュラ性
- 即時通信を行うハードウェアのサイクル精度動作記述モジュール群に対するモデル検査の一手法(FPGAとその応用及び一般)
- 即時通信を行うハードウェアのサイクル精度動作記述モジュール群に対するモデル検査の一手法(FPGAとその応用及び一般)
- 即時通信を行うハードウェアのサイクル精度動作記述モジュール群に対するモデル検査の一手法(FPGAとその応用及び一般)
- 即時通信を行うハードウェアのサイクル精度動作記述モジュール群に対するモデル検査の一手法
- 無線端末の遭遇履歴情報を用いた移動軌跡推定手法の提案
- 多人数参加型アプリケーションにおける品質要求を考慮した帯域制御の一方式(マルチメディア通信と分散処理)
- 動画の品質劣化の許容度を考慮した帯域制御の一方式
- 帯域割譲交渉による動的帯域制御方式
- 品質要求を考慮した動的な帯域制御を行うプロトコルの提案とその性能評価
- コンポーネント連携によるサービスをオーバレイネットワーク上で実現するためのサービス設計技法の提案(セッション8-B : ミドルウェア)
- コンポーネント連携によるサービスをオーバレイネットワーク上で実現するためのサービス設計技法の提案(セッション8-B : ミドルウェア)
- 時間制約付き制御フローグラフの弱双模倣等価性検証およびWebセキュリティ検査への応用(VLSIの設計/検証/テスト及び一般テスト)
- 時間制約付き制御フローグラフの弱双模倣等価性検証およびWebセキュリティ検査への応用(VLSIの設計/検証/テスト及び一般 テスト)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 時間制約付き制御フローグラフの弱双模倣等価性検証およびWebセキュリティ検査への応用(VLSIの設計/検証/テスト及び一般 テスト)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 時間制約付き制御フローグラフの弱双模倣等価性検証およびWebセキュリティ検査への応用(VLSIの設計/検証/テスト及び一般 テスト)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 時間制約付き制御フローグラフの弱双模倣等価性検証およびWebセキュリティ検査への応用
- ノード間の位置関係に基づく推定位置精度の評価手法
- ノード障害に対する自律分散的回復を可能とするオーバレイ遅延最小木の構築アルゴリズム(セッション4:ミドルウェア)
- センサネットワークアプリケーションの実装支援APIの実装と評価
- 安定したストリーム配信を実現するオーバレイマルチキャストプロトコルの設計とPlanetLab上での実証実験
- ワイヤレスデバイスとレーザレンジスキャナを併用した移動体トラッキング(ホームネットワーク,ユビキタスネットワーク,クラウドコンピューティング,コンテキストアウェア,位置情報サービス,eコマース及び一般)
- センサネットワークアプリケーションの実装支援APIの実装と評価
- センサネットワークアプリケーションの実装支援APIの実装と評価
- 無線メッシュネットワークのWDSクラスタ分割問題
- 無線LANのWDSにおけるAP間通信へのリンクスケジューリングアルゴリズムの適用(有線/無線シームレスネットワーク, ネットワーク制御, 無線通信, モバイルネットワーキング, Mobile IP, 一般)
- 無線ネットワークにおける受信確率を考慮したリンクスケジューリングアルゴリズム(モバイルとインターネットの融合, 及び一般)
- 無線ネットワークにおける受信確率を考慮したリンクスケジューリングアルゴリズム(モバイルとインターネットの融合, 及び一般)
- 無線ネットワークにおける受信確率を考慮したリンクスケジューリングアルゴリズム(モバイルとインターネットの融合, 及び一般)
- 無線ネットワークのリンクスケジューリング問題に対するヒューリスティック解法の提案(無線・モバイルネットワーク)(ブロードバンドネットワークサービス)
- 静的及びモバイルマルチキャストルーチング問題に対する最適パス選択解法の提案