×

zbMATH — the first resource for mathematics

“Corner” relations in Allen’s algebra. (English) Zbl 0911.68184
Summary: This paper proves a key result in the maximality proof of ORD-Horn relations, namely, the fact that any subclass of Allen’s algebra which contains all atomic relations, is closed under conversion, intersection and composition, and contains a relation which is not ORD-Horn will contain one (in fact, two at least) of four specific relations, the “corner” relations.
Our proof uses the structural properties of ORD-Horn relations, where the original proof was by machine enumeration.

MSC:
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI