Paper announcement

Dear All,

I would like to advertise the following paper, which is
accepted at the WoLLIC'05.

cheers,
-Ozan

Title: System BV is NP-complete

Abstract:
System BV is an extension of multiplicative linear logic
(MLL) with the rules mix, nullary mix, and a self-dual,
non-commutative logical operator, called seq. While the
rules mix and nullary mix extend the deductive system,
the operator seq extends the language of MLL. Due to the
operator seq, system BV extends the applications of MLL
to those where sequential composition is crucial, e.g.,
concurrency theory. System FBV is an extension of MLL
with the rules mix and nullary mix. In this paper, by
relying on the fact that system BV is a conservative
extension of system FBV, I show that system BV is
NP-complete by encoding the 3-Partition problem in FBV.
I provide a simple completeness proof of this encoding
by resorting to a novel proof theoretical method for
reducing the nondeterminism in proof search, which is
also of independent interest.

http://www.informatik.uni-leipzig.de/~ozan/Papers/BVnpc.pdf