DTD存在下での否定を含まないXPathクエリの恒真性判定
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,DTDが存在するときの,否定を含まないXPath (Positive XPath)クエリの恒真性判定問題について議論する.XPathクエリqとDTD Dが与えられたとき,Dに従うすべてのXML文書TについてTにおけるqの解が空ではないとき,qはDのもとで恒真であるという.恒真性判定問題は,充足可能性や包含性判定問題と同様に,問合せの基本的な静的解析問題のひとつであり,問合せ最適化やデータ交換に有用である.本稿では,まず子軸,子孫軸と述語のみが許されたPositive XPathクエリの恒真性判定が多項式時間で解けることを示す.そして,さらにいくつかの演算子を許すと恒真性の判定が手に負えなくなることを示す.
- 社団法人電子情報通信学会の論文
- 2010-12-07
著者
-
藤原 融
大阪大学大学院情報科学研究科
-
橋本 健二
大阪大学大学院情報科学研究科
-
石原 靖哲
大阪大学大学院情報科学研究科
-
橋本 健二
奈良先端科学技術大学院大学情報科学研究科
-
石原 靖哲
大阪大学大学院基礎工学研究科情報数理系
-
藤原 融
大阪大学大学院基礎工学研究科
-
橋本 健二
奈良先端科学技術大学院大学 情報科学研究科
関連論文
- 公理的安全性の枠組みにおける汎用的結合可能な相互認証と鍵交換の記号的安全性(理論)
- MBRを用いたユーティリティ産業向け日間需要量予測方式の検討
- 静止画の輝度値または周波数領域へ透かし情報を埋め込む形式の電子透かしに対するJPEG圧縮攻撃に関する性能評価と考察(フレッシュマンセッション,フレッシュマンセッション,一般)
- 誤り訂正符号の性能評価(情報通信基礎サブソサイエティ合同研究会)
- ユーザ指定関係に基づいた情報保存を満たすXMLスキーマ進化
- 画素空間へのパッチワーク法と相関型電子透かし法の検出誤り確率の比較(情報セキュリティ応用)
- 評価者間類似度を用いた不正評価排除によるレピュテーションシステムの性能向上(セッション4:コミュニティ(1))
- ネットワーク符号化におけるリード・ソロモン型符号の距離分布について(一般セッション,フレッシュマンセッション,一般)
- BS-5-6 カルテ情報自己管理のための墨塗り署名(BS-5. ネットワークサービスのセキュリティ技術の展開,シンポジウムセッション)
- 最小距離の半分の重みをもつ訂正不可能誤りの数の下界(情報通信基礎サブソサイエティ合同研究会)
- コンテンツ事前配信のための匿名フィンガープリンティング
- 木埋め込み関係に基づくXMLスキーマ進化に応じたXPath問合せ変換(夏のデータベースワークショップ2007(データ工学,一般))
- 木の埋め込み関係に基づくXMLスキーマ進化に応じた文書変換器の生成法(夏のデータベースワークショップ2007(データ工学,一般))
- 木埋め込み関係に基づくXMLスキーマ進化に応じたXPath問合せ変換(XML (1),夏のデータベースワークショップ2007(データ工学,一般))
- 木の埋め込み関係に基づくXMLスキーマ進化に応じた文書変換器の生成法(XML (1),夏のデータベースワークショップ2007(データ工学,一般))
- XMLデータベースにおけるスキーマ進化のための更新操作群とそれらのスキーマ表現能力保存に関する性質(基礎理論,フォーマルアプローチ論文)
- 大学院情報系学生に対する技術者倫理教育(技術者倫理・情報倫理教育の現状と課題,及び一般)
- 2重符号化を用いた電子透かし抽出誤り訂正・検出法
- XMLデータベースへの型推論を用いた攻撃に対する安全性検証(XML,夏のデータベースワークショップDBWS 2006)
- XMLデータベースへの型推論を用いた攻撃に対する安全性検証(XML)
- 大阪大学情報科学研究科におけるソフトウェアデザイン工学高度人材育成への取り組み
- Seguin 下界の局所重み分布を用いた改善
- AP-1-4 線形符号のトレリス構造ならびに重み分布に関する未解決問題(AP-1.情報理論と情報通信における未解決問題 : 簡単そうなのになぜ解けない?,基礎・境界)
- 相関型電子透かしの誤検出確率保証法における見逃し確率の改善
- 検索語の秘匿と検索結果の一貫性検証を可能とするデータ検索プロトコルにおける通信量の削減
- 電子情報通信レクチャーシリーズ C-1 情報・符号・暗号の理論, 今井秀樹(著), "電子情報通信レクチャーシリーズ C-1 情報・符号・暗号の理論", 電子情報通信学会(編), コロナ社(2004-10), B5判, 定価(本体3,500円+税)
- 4-2 情報セキュリティ : 暗号基盤技術の安全性(4. 社会・情報システムの安全, 安全に暮らしたい)
- 情報セキュリティ : 暗号基盤技術の安全性
- Some Results on the Local Weight Distribution of Binary Linear Codes (Algebraic Aspects of Coding Theory and Cryptography)
- タイムカプセル暗号
- 2値多重音響特徴ベクトルを用いた類似音楽探索法の頑健性評価
- 公理的安全性の枠組みにおける汎用的結合可能な相互認証と鍵交換の記号的安全性
- XMLデｰタベｰスにおける表現能力を保存したスキｰマ更新操作
- XMLデータベースにおける表現能力を保存したスキーマ更新操作(Web,XML,文書検索)(データ工学,ディペンダビリティ,一般)
- XMLデータのスキーマ統合のための枠組の提案
- 異なる構造を持つXMLデータを統合するための構造間の関係について(実空間とサイバースペースの融合 : 感性, データベース, ロボティクスおよび一般)
- オブジェクト指向データベースにおける推論攻撃不可能性の逐次的検査法
- 評価者間類似度計算の改善による汚染コンテンツダウンロード抑制効果向上
- The validity problem of positive XPath queries in the presence of DTDs (ソフトウェアサイエンス)
- リード・マラー符号の最小重み部分符号語集合の構造を用いた軟値入出力復号法のシミュレーション結果(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- リード・マラー符号の最小重み部分符号語集合の構造を用いた軟値入出力復号法のシミュレーション結果(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- リード・マラー符号の最小重み部分符号語集合の構造を用いた軟値入出力復号法のシミュレーション結果(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 適応型再帰的最尤復号法の実装とシミュレーション結果(一般,フレッシュマン,招待講演)
- 2元線形符号の最粗な並列・連接形剰余類への分解法に基づく適応的再帰形最尤復号法(モバイル環境におけるPerson to Person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 2元線形符号の最粗な並列・連接形剰余類への分解法に基づく適応的再帰形最尤復号法(モバイル環境におけるPerson to person高信頼性情報流通技術 : 情報通信サブソサイエティ合同研究会)
- 2元線形符号の最粗な並列・連接形剰余類への分解法に基づく適応的再帰形最尤復号法(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 2元線形符号の最粗な並列・連接形剰余類への分解法に基づく適応的再帰形最尤復号法(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 最小距離の半分の重みをもつ訂正不可能誤りの数の下界(情報通信基礎サブソサイエティ合同研究会)
- 最小距離の半分の重みをもつ訂正不可能誤りの数の下界(情報通信基礎サブソサイエティ合同研究会)
- 2元(128,50)拡大原始BCH符号と(128,64)リード・マラー符号の局所重み分布(一般セッション)(フレッシュマン,一般)
- 2元線形符号における記号位置置換不変性を用いた局所距離分布の計算法
- オーディオ信号用のある電子透かしに対する検出誤り確率推定法における精度向上に関する考察
- オーディオ信号用のある電子透かしに対する検出誤り確率推定法における精度向上に関する考察
- オーディオ信号用のある電子透かしに対する検出誤り確率推定法における精度向上に関する考察
- オーディオ信号用のある電子透かしに対する検出誤り確率推定法における精度向上に関する考察
- オーディオ信号への電子透かしにおける検出誤り確率推定について
- 検索効率と汚染コンテンツ抑制の非構造化オーバレイに対する評価指標の検討
- 検索効率と汚染コンテンツ抑制の非構造化オーバレイに対する評価指標の検討
- 評価者間類似度を用いた不正評価排除によるレピュテーションシステムの性能向上(セッション4:コミュニティ(1))
- 評価者間類似度を用いた不正評価排除によるレピュテーションシステムの性能向上(セッション4:コミュニティ(1))
- オブジェクト指向データベースにおける推論攻撃不可能性の逐次的検査法
- Generic Modelにおける困難性仮定への攻撃の数式処理を用いた導出(情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- XMLスキーマで定義された型とXPath式との対応の解析手法
- ユーザ指定関係に基づいた情報保存を満たすXMLスキーマ進化
- XMLデータベースにおける表現能力を保存したスキーマ更新操作(Web,XML,文書検索)(データ工学,ディペンダビリティ,一般)
- 検索語の秘匿と検索結果の一貫性検証を可能とするデータ検索プロトコルにおける通信量の削減
- XMLスキーマで定義された型と XPath 式との対応の解析手法
- マーケティング情報が保護された委託配信システムにおける通信頻度の削減
- マーケティング情報が保護された委託配信システムにおける通信頻度の削減
- Generic Modelにおける困難性仮定への攻撃の数式処理を用いた導出(情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- (64, 35)リード・マラー部分符号の再帰的最尤復号器の復号誤り確率と尤度の計算精度の関係について
- 再帰的MAPアルゴリズム
- 再帰的最尤復号アルゴリズムを用いた誤り訂正復号器のVLSI設計
- 再帰的最尤復号アルゴリズムを用いた誤り訂正復号器のVLSI設計
- 再帰的最尤復号アルゴリズムを用いた誤り訂正復号器のVLSI設計
- Static Adversaryに対してEUC安全な認証の記号的基準について (ワイドバンドシステム・情報通信基礎サブソサイエティ合同研究会)
- Static Adversaryに対してEUC安全な認証の記号的基準について (情報セキュリティ・情報通信基礎サブソサイエティ合同研究会)
- Static Adversaryに対してEUC安全な認証の記号的基準について (情報理論・情報通信基礎サブソサイエティ合同研究会)
- 返信偽造可能性判定問題が決定可能となるための十分条件と判定法
- グループ署名を用いた秘密投票プロトコル
- 誤り訂正符号の性能評価(情報通信基礎サブソサイエティ合同研究会)
- 誤り訂正符号の性能評価(情報通信基礎サブソサイエティ合同研究会)
- GMD復号法とChase復号法における漸近的誤り特性について
- 比較的少ないメモリで線形ブロック符号のコセットリーダの重み分布を求める分割統冶アルゴリズムについて
- On the impossibility of d-multiplicative non-perfect secret sharing (情報セキュリティ)
- タイムカプセル暗号
- 相関型電子透かしの誤検出確率保証法における見逃し確率の改善
- Recovery of tampered pixels for statistical fragile watermarking (マルチメディア情報ハイディング・エンリッチメント)
- Recovery of tampered pixels for statistical fragile watermarking (情報通信システムセキュリティ)
- Recovery of tampered pixels for statistical fragile watermarking (技術と社会・倫理)
- Recovery of tampered pixels for statistical fragile watermarking (情報セキュリティ)
- Static Adversaryに対してEUC安全な認証の記号的基準について(情報通信基礎サブソサイエティ合同研究会)
- Static Adversaryに対してEUC安全な認証の記号的基準について(情報通信基礎サブソサイエティ合同研究会)
- Static Adversaryに対してEUC安全な認証の記号的基準について(情報通信基礎サブソサイエティ合同研究会)
- DTD存在下での否定を含まないXPathクエリの恒真性判定
- コンテンツ事前配信のための匿名フィンガープリンティング
- 多数決論理復号法とOrdered Statistic復号法による2段階復号法の性能解析
- 多数決論理復号法とOrdered Statistic復号法による2段階復号法の性能解析
- PA-2-3 ISCL鍵管理プロトコルの安全性検証
- IT2000-25 誤り訂正符号の性能評価