It is well-known that star-free regular expressions, which are defined by the grammar
$r::= a \mid r \cdot r \mid r \cup r \mid \neg r \mid \varepsilon \mid \emptyset$
where $a$ belongs to a finite alphabet $\Sigma$ and $\varepsilon$ is the empty string, have their language-emptiness problem which is non-elementary (more precisely, tower-complete), being negation the "difficult case".
However, what can we say about the same problem for this kind of regular expressions?
$r::= a \mid r \cdot \Sigma^+ \mid \Sigma^+\cdot r \mid r \cup r \mid \neg r \mid\varepsilon \mid \emptyset$
Here, we still have negation, and still no Kleene star, as $\Sigma^+$ can be "rewritten" as $\neg(\emptyset \cup \varepsilon)$, but concatenation is weakened: in fact, $r \cdot \Sigma^+$ and $\Sigma^+\cdot r$ represent right-/left-extensions of $r$ with any (non-empty) string.
Does anybody know the complexity of this problem? Is it elementary? Do you know similar problems/connected literature? Thanks.