Provability in TBLL: A decision procedure

From MaRDI portal





The recently proved (1990) undecidability of propositional linear logic provided a special interest in determining the complexity of its different fragments. The present paper investigates the tensor-bang fragment of linear logic (TBLL) using a direct analysis of deduction in TBLL in the spirit of formal language theory. The TBLL language consists of a (linearly ordered) set \(\Sigma\) of propositional letters, the logical constants being the binary connective ``tensor and the unary (prefix) connective ``bang (called also ``of course). Using their previous result on testing sequents in the fragment TBLL\(-\)TLL, the authors provide an algorithm that decides the derivability of a TBLL sequent \(L\lvdash \alpha\) in \(O(n^{2n^ 2})\) steps, where \(n=\text{length}(L)+\text{length}(\alpha)\), and \(L\), \(\alpha\in\text{TBLL}\). For the entire collection see [Zbl 0772.68004].











This page was built for publication: Provability in TBLL: A decision procedure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4202932)