Portal de Periódicos da CAPES

On the Complexity of Linearizability

2015; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-319-26850-7_21

1611-3349

Jad Hamza,

semigroups and automata theory

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