  The choice of the right trade-off between expressiveness and complexity is
the main issue in interval temporal logic. In their seminal paper, Halpern and
Shoham showed that the satisfiability problem for HS (the temporal logic of
Allen's relations) is highly undecidable over any reasonable class of linear
orders. In order to recover decidability, one can restrict the set of temporal
modalities and/or the class of models. In the following, we focus on the
satisfiability problem for HS fragments under the homogeneity assumption,
according to which any proposition letter holds over an interval if only if it
holds at all its points. The problem for full HS with homogeneity has been
shown to be non-elementarily decidable, but its only known lower bound is
EXPSPACE (in fact, EXPSPACE-hardness has been shown for the logic of prefixes
and suffixes BE, which is a very small fragment of it. The logic of prefixes
and infixes BD has been recently shown to be PSPACE-complete. In this paper, we
prove that the addition of the Allen relation Meets to BD makes it
EXPSPACE-complete.
