Relation algebras of intervals

摘要

Given a representation of a relation algebra we construct relation algebras of pairs and of intervals. If the representation happens to be complete, homogeneous and fully universal then the pair and interval algebras can be constructed direct from the relation algebra. If, further, the original relation algebra is ω-categorical we show that the interval algebra is too. The complexity of relation algebras is studied and it is shown that every pair algebra with infinite representations is intractable. Applications include constructing an interval algebra that combines metric and interval expressivity.