Abstract |
We embed Safe Recursion on Notation (SRN) into Light Affine Logic by Levels (LALL), derived from the logic ML4. LALL is an intuitionistic deductive system, with a polynomial time cut elimination strategy. The embedding allows to represent every term t of SRN as a family of nets in LALL. Every net in the family simulates t on arguments whose bit length is bounded by the index of the net. The embedding is based on two crucial features. One is the recursive type in LALL that encodes Scott binary numerals, i.e. Scott words, as nets. Scott words represent the arguments of t in place of the more standard Church binary numerals. Also, the embedding exploits the "fuzzy" borders of paragraph boxes that LALL inherits from ML4 to "freely" duplicate the arguments, especially the safe ones, of t. Finally, the type of the net depends on the number of composition and recursion schemes used to define t, namely the structural complexity of t. Moreover, the size of the net is a polynomial in the index of the net in the family, whose degree depends on the structural complexity of t. So, this work makes closer both the predicative recursive theoretic principles SRN relies on, and the proof theoretic one, called stratification, at the base of Light Linear Logic. |
@inproceedings{Roversi+Vercelli:2010-DICE10,
volume = {23},
author = {Roversi, Luca and Vercelli, Luca},
series = {{Electronic Proceedings in Theoretical Computer Science}},
booktitle = {{Proceedings of the Workshop on Developments in Implicit
Computational complexity (DICE 2010)}},
url = {http://www.di.unito.it/~rover/RESEARCH/PUBLICATIONS/2010-DICE/RoversiVercelli2010DICE.pdf},
title = {{Safe Recursion on Notation into a Light Logic by Levels}},
abstract = {We embed Safe Recursion on Notation (SRN) into Light Affine Logic
by Levels (LALL), derived from the logic ML4. LALL is an
intuitionistic deductive system, with a polynomial time cut
elimination strategy. The embedding allows to represent every term
t of SRN as a family of nets in LALL. Every net in the family
simulates t on arguments whose bit length is bounded by the index
of the net. The embedding is based on two crucial features. One is
the recursive type in LALL that encodes Scott binary numerals,
i.e. Scott words, as nets. Scott words represent the arguments of
t in place of the more standard Church binary numerals. Also, the
embedding exploits the "fuzzy" borders of paragraph boxes that
LALL inherits from ML4 to "freely" duplicate the arguments,
especially the safe ones, of t. Finally, the type of the net
depends on the number of composition and recursion schemes used to
define t, namely the structural complexity of t. Moreover, the
size of the net is a polynomial in the index of the net in the
family, whose degree depends on the structural complexity of t.
So, this work makes closer both the predicative recursive
theoretic principles SRN relies on, and the proof theoretic one,
called stratification, at the base of Light Linear Logic. },
pages = {63 -- 77},
year = {2010},
}
This document was generated by bib2html 3.3.
(Modified by Luca Paolini, under the GNU General Public License)