| 講演名 | 1999/6/18 2本の時間軸間の時間的推論 石原 靖哲, 石井 信, 関 浩之, 伊藤 実, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では,2本の時間軸間の制約式に関する推論問題について述べる.まず,このような制約式の無矛盾性判定問題がNP完全であることを示す.次に,本稿では,制約式のグラフ表現の概念を導入する.もし,与えられた制約式cのグラフ表現が多項式時間で構成可能ならば,cの無矛盾性も多項式時間で判定できる.しかし,cがグラフ表現をもつかどうかの判定問題は一般にcoNP完全である.そこで,本稿では,グラフ表現が多項式時間で構成可能な制約式の部分クラスを提案する.このクラスは,これまで無矛盾性判定問題が多項式時間で解けることが知られているどのような制約式のクラスにも包含されない. |
| 抄録(英) | This paper discusses temporal reasoning about constraints between two time axes. First, we mention that the consistency of such constraints is NP-complete. Then, we introduce the notion of graph representations of constraints. If a graph representation of a given constraint c can be constructed in polynomial time, then the consistency of c is solvable in polynomial time. However, it is shown that the graph representability of a given c is coNP-complete. Next, we propose a subclass K of constraints such that for each constraint c in K, a graph representation of c can be constructed in polynomial time. The expressive power of K is incomparable with any other subclasses for which the consistency problem is known to be tractable. |
| キーワード(和) | 時間的推論 / 時間的制約 / 無矛盾性 / 大域時刻 / 局所時刻 |
| キーワード(英) | temporal reasoning / temporal constraint / consistency / global time / local time |
| 資料番号 | COMP99-17 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1999/6/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 2本の時間軸間の時間的推論 |
| サブタイトル（和） | |
| タイトル（英） | Temporal Reasoning between Two Time Axes |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 時間的推論 / temporal reasoning |
| キーワード(2)（和/英） | 時間的制約 / temporal constraint |
| キーワード(3)（和/英） | 無矛盾性 / consistency |
| キーワード(4)（和/英） | 大域時刻 / global time |
| キーワード(5)（和/英） | 局所時刻 / local time |
| 第 1 著者 氏名（和/英） | 石原 靖哲 / Yasunori ISHIHARA |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology |
| 第 2 著者 氏名（和/英） | 石井 信 / Shin ISHII |
| 第 2 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology |
| 第 3 著者 氏名（和/英） | 関 浩之 / Hiroyuki SEKI |
| 第 3 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology |
| 第 4 著者 氏名（和/英） | 伊藤 実 / Minoru ITO |
| 第 4 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology |
| 発表年月日 | 1999/6/18 |
| 資料番号 | COMP99-17 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 130 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |