60 citations · 157 across the 17 of their papers we have counts for
5 papers · 1 filter
A New Linear Time Correctness Condition for Multiplicative Linear Logic
Satoshi Matsuoka
In this paper, we give a new linear time correctness condition for proof nets of Multiplicative Linear Logic without units. Our approach is based on a rewriting system over trees.…
A New Proof of P-time Completeness of Linear Lambda Calculus
Satoshi Matsuoka
We give a new proof of P-time completeness of Linear Lambda Calculus, which was originally given by H. Mairson in 2003. Our proof uses an essentially different Boolean type from th…
P-time Completeness of Light Linear Logic and its Nondeterministic Extension
Satoshi Matsuoka
In CSL'99 Roversi pointed out that the Turing machine encoding of Girard's seminal paper "Light Linear Logic" has a flaw. Moreover he presented a working version of the encoding in…
Nondeterministic Linear Logic
Satoshi Matsuoka
In this paper, we introduce Linear Logic with a nondeterministic facility, which has a self-dual additive connective. In the system the proof net technology is available in a natur…
Weak Typed Boehm Theorem on IMLL
Satoshi Matsuoka
In the Boehm theorem workshop on Crete island, Zoran Petric called Statman's ``Typical Ambiguity theorem'' typed Boehm theorem. Moreover, he gave a new proof of the theorem based o…