[Prev][Next][Index][Thread]

complexity





Does anybody know the complexity of provability for non commutative  
multiplicative linear logic with units but without atoms?

 The formulae are built from Unit and Bottom using Times and Par.
 The rules are:

                    |- GAMMA, A, GAMMA'    |- DELTA, B, DELTA' 

    -------         ------------------------------------------
    |- Unit         |- DELTA, GAMMA, A Times B, DELTA', GAMMA'

        |- GAMMA, GAMMA'              |- GAMMA, A, B, GAMMA'
    ------------------------         -------------------------
    |- GAMMA, Bottom, GAMMA'         |- GAMMA, A Par B, GAMMA'

 In the Times rule, GAMMA' or DELTA must be empty.

Yves Lafont <lafont@lmd.univ-mrs.fr>.