@Article{ vigano:on:2000-b, author = {Luca Vigan{\`o}}, title = {An ${O}(n \log n)$-space decision procedure for the relevance logic $\mathrm{B^+}$}, journal = {Studia Logica}, year = 2000, volume = 66, number = 3, pages = {385--407}, language = {USenglish}, abstract = {In previous work we gave a new proof-theoretical method for establishing upper-bounds on the space complexity of the provability problem of modal and other propositional non-classical logics. Here we extend and refine these results to give an O(n log n) decision procedure for the basic positive relevance logic $\mathrm{B^+}$. We compute this upper-bound by first giving a sound and complete, cut-free, labelled sequent system for $\mathrm{B^+}$, and then establishing bounds on the application of the rules of this system.}, ps = {papers/2000/Vsl00.ps.gz}, pdf = {papers/2000/Vsl00.pdf}, filelabel = {Extended version: Technical report No. 140}, file = {http://www.informatik.uni-freiburg.de/tr/} }