  It was shown in Alur et al. [1] that the problem of verifying finite
concurrent systems through Linearizability is in EXPSPACE. However, there was
still a complexity gap between the easy to obtain PSPACE lower bound and the
EXPSPACE upper bound. We show in this paper that Linearizability is
EXPSPACE-complete.
