2
$\begingroup$

I'm studying continuous CSP from the slides of my professor and i got that with the PATH-CONSISTENCY algorithm you can check consistency for PA (Point Algebra), SIA and ORD-Horn; however it cannot be used to determine consistency for IA (Interval Algebra), since it is just a necessary but not sufficient condition. From this i would say that it must exist a IA Network which is path consistent, but not consistent. However i cannot construct such a network. Is my assumption wrong? If not what would be an example of a IA network which is path consistent but not consistent?

$\endgroup$
2
$\begingroup$

Yes, you are correct.

Here is the classic example of an interval algebra network that is path consistent, but not consistent. It appears in Allen, James F. (26 November 1983) "Maintaining knowledge about temporal intervals". Communications of the ACM. ACM Press: 832–843. doi:10.1145/182.358434.

enter image description here

It seems the arc between interval $B$ and $C$ in the above figure is missing its arrowhead. However, you can assign either direction to that arrow since the relationship $(d\ di)$ is symmetric.

It should be noted that this algorithm, while it does not generate inconsistencies, does not detect all inconsistencies in its input. In fact, it only guarantees consistency between three node subnetworks. There are networks that can be added which appear consistent by viewing any three nodes, but for which there is no consistent overall labeling. The network shown in Figure 5 is consistent if we consider any three nodes; however, there is no overall labeling of the network. To see this, if we assign the relationship between $A$ and $C$, which could be $f$ or $fi$ according to this network, to either $f$ alone, or $fi$ alone, we would arrive at an inconsistency. In other words, there is no consistent labeling with $A-(f)\to C$, or with $A-(fi)\to C$, even though the algorithm accepts $A-(f\ fi)\to C$.

I would encourage you to read that seminal paper by Allen for more information.

$\endgroup$
  • $\begingroup$ Thank you a lot (also for the reference to the article, it was very helpful). However i still have a doubt: i can see, using the rule of composition for relations in IA, that the network you posted is path-consistent but how can i check that it is inconsistent? I have to try all the combinations and see that what i get is inconsistent? $\endgroup$ – Marco Cadei Dec 28 '18 at 7:34
  • 1
    $\begingroup$ Yes, basically, you have to try all combinations, which is pretty easy, actually. Draw intervals to represent all nodes. Start from the relationship between $D$ and $B$. Check where you can put $A$ and $C$. You will see easily that $A$ and $C$ cannot finish at the same point of time. $\endgroup$ – Apass.Jack Dec 28 '18 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.