アレンの区間代数

アレンの区間代数は、1983 年にJames F. Allenによって導入された時間的推論のための計算です。

計算は、時間間隔間の可能な関係を定義し、イベントの時間的記述についての推論の基礎として使用できる構成表を提供します。

次の 13 個の基本関係は、2 つの区間間の可能な関係を捉えます。

この計算を使用すると、与えられた事実を形式化し、自動推論に使用することができます。区間間の関係は、基本関係のセットとして形式化されます。

文章

夕食の間、ピーターは新聞を読みます。その後、寝ます。

は、アレンの区間代数で次のように形式化されます。

${\displaystyle {\mbox{新聞}}\mathbf {\{\operatorname {d} \}} {\mbox{夕食}}}$

${\displaystyle {\mbox{夕食}}\mathbf {\{\operatorname {<} \}} {\mbox{ベッド}}}$

一般に、 n = 0 から始まるn 個の区間間の異なる関係の数は、 1、1、13、409、23917、2244361... OEIS A055203 です。上記の特殊なケースは、n  = 2 の場合です。

時間間隔間の関係を推論するために、アレンの区間代数は合成表を提供します。との関係、およびとの関係が与えられている場合、合成表によりと の関係について結論付けることができます。逆演算と組み合わせると、アレンの区間代数は関係代数に変換されます。 ${\displaystyle X}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle X}$${\displaystyle Z}$

たとえば、次のように推測できます。 ${\displaystyle {\mbox{新聞}}\mathbf {\{\operatorname {<} \}} {\mbox{ベッド}}}$

アレンの区間代数は、時間間隔と空間構成の両方の記述に使用できます。後者の用途では、関係は空間オブジェクトの相対的な位置を記述するものとして解釈されます。これは、各座標の関係を個別にリストすることで、3 次元オブジェクトにも適用できます。

重複マークアップの研究では同様の代数が使用されています（^[1]を参照）。そのモデルは、文書構造のエンドポイントが実際に共存できるかどうか、または単に[接線]であるかどうかに応じて、より多くのバリエーションがあります。

文化遺産オントロジーCIDOC CRMでは、アレン関係はいわゆる時間プリミティブに置き換えられ、証明可能なステートメントの作成とこれらのステートメントについての推論を容易にします。^[2] 時間プリミティブは、アレン関係を間隔の開始または終了に関する個別のステートメントに分割します。たとえば、XがY（）と重複する場合は、次のように分割できます。 ${\displaystyle X\mathbf {\演算子名 {o} } Y}$

• ${\displaystyle X\mathbf {\演算子名 {o} } Y}$≡ ( 、 )の開始前に始まります∧ ( 、)の開始後に終わります∧ ( 、)の終了前に終わります${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$

さらに、アレン関係のと等しい は、または の前では に、 またはの後ろではに置き換えられます。簡単な例:

• ハロルド2世 の治世はヘイスティングズの戦いが始まる前に始まった。
• ハロルド2世の治世/生涯はヘイスティングズの戦いの開始とともに終了した。
• ハロルド2世の治世/生涯はヘイスティングズの戦いの終結前または終結とともに終わる。

この例では、ハロルド 2 世が戦闘の開始時、戦闘中、または戦闘終了時に殺害されたかどうか、つまり、、またはが適用されるかどうかを指定する必要はありません(などの論理和は、クエリ以外では CIDOC CRM では表現できません)。特定の歴史的質問に関連する場合は、たとえばの開始後に を追加することで、後で指定できます。 ${\displaystyle X\mathbf {\operatorname {m} } Y}$${\displaystyle X\mathbf {\演算子名 {o} } Y}$${\displaystyle X\mathbf {\operatorname {fi} } Y}$${\displaystyle \mathbf {\{\オペレータ名 {m} ,\オペレータ名 {o} ,\オペレータ名 {fi} \}} }$

CIDOC CRM は、イベントとそれに対応する時間間隔を区別します。アレン関係と時間プリミティブは、イベント間のステートメントであり、時間間隔間の結果としてのみ存在します。もう 1 つの違いは、CIDOC CRM の時間、空間、時空間エンティティがあいまいな境界を持つと見なされることです。特に、正確な同時性に関するステートメントは、それ以外の場合は極めてまれです。

• Allen の時間関係の概念とパス一貫性アルゴリズムを実装したシンプルな Java ライブラリ
• Allen の区間代数を実装する Java ライブラリ (データとインデックス構造 (例:区間ツリー) を含む)
• OWL-Time は、OWL のタイム オントロジーであり、世界中のリソースまたは Web ページで説明されているリソースの時間的特性を表すための時間概念のOWL -2 DL オントロジーです。
• GQR は、アレンの区間代数 (およびその他多数) の推論システムです。
• qualreas は、RCC-8、Allen の区間代数、および時間ポイントと統合され、左分岐時間または右分岐時間に位置する Allen 代数などの関係代数のネットワーク上で定性的な推論を行うための Python フレームワークです。
• SparQはアレンの区間代数（およびその他多数）の推論エンジンです。
• EveXL は、ASCII アート パターンを介して区間代数の演算子を実装する、イベント検出用の小さなドメイン固有言語です。

• 時間的論理
• 論理
• 領域接続計算
• 空間関係（アナログ）
• 常識的な推論

• Allen, James F. (1983 年 11 月 26 日). 「時間間隔に関する知識の維持」(PDF) . Communications of the ACM . 26 (11): 832–843. CiteSeerX  10.1.1.472.5244 . doi :10.1145/182.358434. hdl :1802/10574. ISSN  0001-0782. S2CID  16729000.
• Nebel, Bernhard ; Bürckert, Hans-Jürgen (1995). 「時間関係についての推論: Allen の区間代数の最大限に扱いやすいサブクラス」(PDF) . Journal of the ACM . 42 : 43–66. doi : 10.1145/200836.200848 . S2CID  6586759.
• van Beek, Peter; Manchak, Dennis W. (1996). 「時間的推論のためのアルゴリズムの設計と実験的分析」(PDF) . Journal of Artificial Intelligence Research . 4 (1996): 1–18. arXiv : cs/9601101 . Bibcode :1996cs......1101V. doi :10.1613/jair.232. S2CID 3204600. 2017年7月6日時点の オリジナル(PDF)からアーカイブ。 2017年5月6日閲覧。