Allen's interval algebra: Difference between revisions

Revision as of 22:07, 31 December 2024

Latest revision as of 22:08, 31 December 2024

(One intermediate revision by the same user not shown)

Line 59:

|X is equal to Y

|}

|}Using this calculus, given facts can be formalized and then used for automatic reasoning. Relations between intervals are formalized as sets of base relations.

To see that the 13 relations are exhaustive, consider note that each point of <math>X</math> can be at 5 possible locations relative to <math>Y</math>: before, at the start, within, at the end, after. These give <math>5 + 4 + 3 + 2 + 1 = 15</math> possible relative positions for the start and the end of <math>X</math>. Of these, we cannot have <math>X_0 = X_1 = Y_0</math> since <math>X_0 < X_1</math>, and similarly we cannot have <math>X_0 = X_1 = Y_1</math>, thus giving us 13 possible relations.

In general, the number of different relations between ''n'' intervals, starting with ''n''&nbsp;=&nbsp;0, is 1, 1, 13, 409, 23917, 2244361... [http[oeis://oeis.org/A055203 |OEIS A055203]]. The special case shown above is for ''n''&nbsp;=&nbsp;2.

===Composition of relations between intervals===

For reasoning about the relations between temporal intervals, Allen's interval algebra provides a [[Relation composition|composition]] table. Given the relation between <math>X</math> and <math>Y</math> and the relation between <math>Y</math> and <math>Z</math>, the composition table allows for concluding about the relation between <math>X</math> and <math>Z</math>. Together with a [[converse relation|converse]] operation, this turns Allen's interval algebra into a [[relation algebra]].

|}Using this calculus, given facts can be formalized and then used for automatic reasoning. Relations between intervals are formalized as sets of base relations.

The sentences

Line 68 ⟶ 76:

<math>\mbox{dinner } \mathbf{\{ \operatorname{<} \}} \mbox{ bed}</math>

In general, the number of different relations between ''n'' intervals, starting with ''n''&nbsp;=&nbsp;0, is 1, 1, 13, 409, 23917, 2244361... [http://oeis.org/A055203 OEIS A055203]. The special case shown above is for ''n''&nbsp;=&nbsp;2.

To see that the 13 relations are exhaustive, consider note that each point of <math>X</math> can be at 5 possible locations relative to <math>Y</math>: before, at the start, within, at the end, after. These give <math>5 + 4 + 3 + 2 + 1 = 15</math> possible relative positions for the start and the end of <math>X</math>. Of these, we cannot have <math>X_0 = X_1 = Y_0</math> since <math>X_0 < X_1</math>, and similarly we cannot have <math>X_0 = X_1 = Y_1</math>, thus giving us 13 possible relations.

===Composition of relations between intervals===

For reasoning about the relations between temporal intervals, Allen's interval algebra provides a [[Relation composition|composition]] table. Given the relation between <math>X</math> and <math>Y</math> and the relation between <math>Y</math> and <math>Z</math>, the composition table allows for concluding about the relation between <math>X</math> and <math>Z</math>. Together with a [[converse relation|converse]] operation, this turns Allen's interval algebra into a [[relation algebra]].

For the example, one can infer <math>\mbox{newspaper } \mathbf{\{ \operatorname{<} \}} \mbox{ bed}</math>.