We propose a characterization of PSPACE by means of atype assignment for an extension
of lambda calculus with a conditional construction. The type assignment STAB is an …

We describe the functions computed by boolean circuits in NC k by means of functions
algebra for k≥ 1 in the spirit of implicit computational complexity. The whole hierarchy …

Using a proofs-as-programs correspondence, Terui was able to compare two models of
parallel computation: Boolean circuits and proof nets for multiplicative linear logic. Mogbil et …

Abstract We introduce Non-deterministic Boolean proof nets to study the correspondence
with Boolean circuits, a parallel model of computation. We extend the cut elimination of Non …

This research in Theoretical Computer Science extends the gateways between Linear Logic
and Complexity Theory by introducing two innovative models of computation. It focuses on …

We introduce LEM, a type-assignment system for the linear λ-calculus that extends second-
order IMLL 2, ie, intuitionistic multiplicative Linear Logic, by means of logical rules that …

We consider a new notion of circuit uniformity based on the concept of rational relations,
called Rational-uniformity and denoted Rat. Our goal is to prove it is sharper than DLogTime …

L'objectif de ce mémoire est d'établir une connexion formelle entre deux modèles
canoniques du calcul parallèle, à savoir les circuits booléens et les réseaux de preuves …

This thesis explores the benefits of non-laziness in both Implicit Computational Complexity
and probabilistic computation. More specifically, this thesis can be divided in two main parts …

Linear Logic and Sub-Polynomial Classes of Complexity Page 1 Université Paris :3 Sorbonne
Paris Cité Laboratoire d’Informatique de Paris Nord Logique linéaire et classes de complexité …