アレンの区間代数

アレンの区間代数（アレンのくかんだいすう、）は、が1983年に提唱した、時間区間に関する計算体系であり、時間的推論のためのものである。

この計算体系は、時間区間の間に成り立ちうる関係を定義し、事象の時間的な記述についての推論の基礎として使える合成表を提供する。

形式的な記述

関係

以下の13個の基本関係が、2つの区間の間に成り立ちうる関係のすべてを捉えている。

関係図示解釈 XはYに先行する（X precedes Y） YはXに先行される（Y is preceded by X） XはYに接する（X meets Y） YはXに接される（Y is met by X。iは「inverse」（逆）を表す） XはYと重なる（X overlaps with Y） YはXに重ねられる（Y is overlapped by X） XはYと共に始まる（X starts Y） YはXにより始められる（Y is started by X） XはYの間にある（X during Y） YはXを含む（Y contains X） XはYと共に終わる（X finishes Y） YはXにより終えられる（Y is finished by X） XとYは等しい（X is equal to Y）

この13個の関係が全てを尽くしていることを確かめるには、の各端点がに対して取りうる相対的な位置が、「前」「開始点」「内部」「終了点」「後」の5通りであることに注目すればよい。これにより、の開始点と終了点の相対的な位置の組み合わせは通りとなる。このうち、であることからとなることはあり得ず、同様にとなることもあり得ないため、結果として13個の関係が得られる。

一般に、n個の区間の間に成り立ちうる異なる関係の個数は、n = 0から始めて 1, 1, 13, 409, 23917, 2244361… となる（OEIS A055203）。上記の特別な場合はn = 2に相当する。

区間間の関係の合成時間区間の間の関係についての推論のために、アレンの区間代数は関係の合成の表を提供する。との間の関係、およびとの間の関係が与えられると、この合成表を用いてとの間の関係を結論づけることができる。逆関係の演算とあわせることで、アレンの区間代数は関係代数となる。

この計算体系を用いることで、与えられた事実を形式化し、自動推論に利用できる。区間の間の関係は、基本関係の集合として形式化される。

夕食の間、ピーターは新聞を読む。その後、彼は寝床に就く。

という文は、アレンの区間代数では次のように形式化される。

この例では、であることが推論できる。

拡張アレンの区間代数は、時間区間と空間的配置の両方の記述に用いることができる。後者の用途では、これらの関係は空間的物体の相対的な位置を記述するものとして解釈される。各座標について別々に関係を列挙することで、三次元の物体についても同様に成り立つ。

の研究では、これと類似した代数が用いられているSteven DeRose. Markup Overlap: A Review and a Horse. In Proceedings of Extreme Markup Languages 2004, Montréal, Québec, August 2–6, 2004. http://xml.coverpages.org/DeRoseEML2004.pdf。そのモデルは、文書構造の端点が真に同一の位置を占めることを許すか、あるいは単に接する（tangent）だけかによって、より多くのバリエーションを持つ。

時間的基本要素

文化遺産オントロジーであるCIDOC概念参照モデルでは、アレンの関係は「時間的基本要素」（temporal primitives）と呼ばれるものに置き換えられている。これにより、立証可能な言明の定式化や、それらの言明についての推論が容易になるCIDOC CRM Version 7.3: https://cidoc-crm.org/versions-of-the-cidoc-crm, section Temporal Relation Primitives based on fuzzy boundaries。時間的基本要素は、アレンの関係を、区間の開始点または終了点についての個々の言明へと分解する。例えば、「XはYと重なる」（）は次のように分解できる。

⇔ 「はの開始より前に始まる」∧「がの開始より後に終わる」∧「がの終了より前に終わる」

さらに、アレンの関係における「等しい」は、「以前もしくは同時」（before or with）および「以後もしくは同時」（after or with）に置き換えられる。簡単な例を挙げる。

ハロルド2世の治世は、ヘイスティングズの戦いの開始よりも前に始まる。ハロルド2世の治世・生涯は、ヘイスティングズの戦いの開始以後もしくは同時に終わる。ハロルド2世の治世・生涯は、ヘイスティングズの戦いの終了以前もしくは同時に終わる。

この例では、ハロルド2世が戦いの開始時、途中、終了時のいずれに殺されたか、すなわち、、のいずれが成り立つかを特定する必要はない（のような選言はCIDOC CRMでは、クエリの場合を除き表現できない）。特定の歴史的な問いにとって重要であれば、例えば「Yの開始より後に終わる」を追加することで後から明示できる。

CIDOC CRMは、事象とそれに対応する時間区間とを区別する。アレンの関係および時間的基本要素は、事象の間の言明であり、それらの時間区間の間の言明はその帰結にすぎない。もう一つの違いは、CIDOC CRMにおける時間的・空間的・時空間的な実体は、あいまいな境界を持つものとして扱われることである。特に、厳密な同時性についての言明は、それ以外の場合には極めて稀である。

実装アレンの時間関係の概念と経路無矛盾性アルゴリズムを実装した簡単なJavaライブラリアレンの区間代数を実装したJavaライブラリ（データ構造・索引構造を含む。例えば区間木） OWL-Time Time Ontology in OWL - 世界における、あるいはウェブページに記述されたリソースの時間的性質を記述するための、OWL-2 DLによる時間概念のオントロジー。 GQR - アレンの区間代数（および他の多く）のための。 qualreas - RCC-8、アレンの区間代数、および左分岐時間・右分岐時間のいずれかに位置付けられ時点と統合されたアレンの代数など、関係代数のネットワークについての定性推論のためのPythonフレームワーク。 SparQ - アレンの区間代数（および他の多く）のための推論器。 EveXL - ASCIIアートのパターンを通じて区間代数の演算子を実装した、事象検出のための小さなドメイン固有言語。

アレンの区間代数

Źródło i licencja