  A classic result by Stockmeyer gives a non-elementary lower bound to the
emptiness problem for star-free generalized regular expressions. This result is
intimately connected to the satisfiability problem for interval temporal logic,
notably for formulas that make use of the so-called chop operator. Such an
operator can indeed be interpreted as the inverse of the concatenation
operation on regular languages, and this correspondence enables reductions
between non-emptiness of star-free generalized regular expressions and
satisfiability of formulas of the interval temporal logic of chop under the
homogeneity assumption. In this paper, we study the complexity of the
satisfiability problem for suitable weakenings of the chop interval temporal
logic, that can be equivalently viewed as fragments of Halpern and Shoham
interval logic. We first consider the logic $\mathsf{BD}_{hom}$ featuring
modalities $B$, for \emph{begins}, corresponding to the prefix relation on
pairs of intervals, and $D$, for \emph{during}, corresponding to the infix
relation. The homogeneous models of $\mathsf{BD}_{hom}$ naturally correspond to
languages defined by restricted forms of regular expressions, that use union,
complementation, and the inverses of the prefix and infix relations. Such a
fragment has been recently shown to be PSPACE-complete . In this paper, we
study the extension $\mathsf{BD}_{hom}$ with the temporal neighborhood modality
$A$ (corresponding to the Allen relation \emph{Meets}), and prove that it
increases both its expressiveness and complexity. In particular, we show that
the resulting logic $\mathsf{BDA}_{hom}$ is EXPSPACE-complete.
