Mathematics – Category Theory
Scientific paper
2004-02-26
Mathematics
Category Theory
27 pages
Scientific paper
In this paper the complexity of provability of polarized additive, multiplicative, and exponential formulas in the (initial) Cockett-Seely polarized game logic is discussed. The complexity is ultimately based on the complexity of finding a strategy in a formula which is, for polarized additive formulas, in the worst case linear in their size. Having a proof of a sequent is equivalent to having a strategy for the internal-hom object. In order to show that the internal-hom object can have size exponentially larger than the formulas of the original sequent we develop techniques for calculating the size of the multiplicative formulas. The structure of the internal hom object can be exploited and, using dynamic programming techniques, one can reduce the cost of finding a strategy in such a formula to the order of the product of the sizes of the original formulas. The use of dynamic techniques motivates the consideration of games as acyclic graphs and we show how to calculate the size of these graph games for the multiplicative and additive fragment and, thus, the cost of determining their provability using this dynamic programming approach. The final section of the paper points out that, despite the apparent complexity of the formulas, there is, for the initial polarized logic with all the connectives (additives, multiplicatives, and exponentials) a way of determining provability which is \emph{linear} in the size of the formulas.
Cockett J. R. B.
Pastro Craig A.
No associations
LandOfFree
On the complexity of Cockett-Seely polarized games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the complexity of Cockett-Seely polarized games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the complexity of Cockett-Seely polarized games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-294423