Reference. Fractional Types: Expressive and Safe Space Management for Ancilla Bits
Cite
Cites 27 works (4 here)
With notes (4)
Integrating Linear and Dependent Types krishnaswami_integrating_2015
Remarks on isomorphisms in typed lambda calculi with empty and sum types fiore-2006-remarks
A mixed linear and non-linear logic: Proofs, terms and models: Extended abstract bentonMixedLinearNonlinear1995
Intuitionistic linear logic regains the expressive power of intuitionistic logic through the ! (‘of course’) modality. Benton, Bierman, Hyland and de Paiva have given a term assignment system for ILL and an associated notion of categorical model in which the ! modality is modelled by a comonad satisfying certain extra conditions. Ordinary intuitionistic logic is then modelled in a cartesian closed category which arises as a full subcategory of the category of coalgebras for the comonad. This paper attempts to explain the connection between ILL and IL more directly and symmetrically by giving a logic, term calculus and categorical model for a system in which the linear and non-linear worlds exist on an equal footing, with operations allowing one to pass in both directions. We start from the categorical model of ILL given by Benton, Bierman, Hyland and de Paiva and show that this is equivalent to having a symmetric monoidal adjunction between a symmetric monoidal closed category and a cartesian closed category. We then derive both a sequent calculus and a natural deduction presentation of the logic corresponding to the new notion of model.
External (23)
- The classification of reversible bit operations (2017)
- Computing with semirings and weak rig groupoids (2016)
- Interpretation and programming of the reversible functional language RFUN (2015)
- Ricercar: A Language for Describing and Rewriting Reversible Circuits with Ancillae and Its Permutation Semantics (2015)
- Arrow: A Modern Reversible Programming Language (2015)
- Quipper: a scalable quantum programming language (2013)
- Isomorphic interpreters from logically reversible abstract machines (2013)
- Superstructural Reversible Logic (2013)
- Information effects (2012)
- Towards a reversible functional language (2012)
- Dagger traced symmetric monoidal categories and reversible programming (2011)
- A categorical presentation of quantum computation with anyons (2010)
- A reversible programming language and its invertible self-interpreter (2007)
- A structural approach to reversible computation (2005)
- Isomorphisms of generic recursive polynomial types (2004)
- Geometry of Interaction and linear combinatory algebras (2002)
- Conservative logic (1982)
- Reversible computing (1980)
- Many-variable functorial calculus. I (1972)
- Coherence for distributivity (1972)
- Algèbre élémentaire dans les catégories avec multiplication (1964)
- Natural associativity and commutativity (1963)
- Catégories avec multiplication (1963)