The Complexity of Revision
G. Aldo Antonelli · Notre Dame Journal of Formal Logic · 1994
In this paper we show that the Gupta-Belnap systems $\mathbf{S}^{＃}$ and ${\bf S}^*$ are $\Pi^1_2$. Since Kremer has independently established that they are $\Pi^1_2$-hard, this completely settles the problem of their complexity. The above-mentioned upper bound is established through a reduction to countable revision sequences that is inspired by, and makes use of a construction of McGee.