Abstract
Elementary Affine Logic (EAL) is a variant of the Linear Logic characterizing the computational power of the elementary bounded Turing machines. The EAL Type Inference problem is the problem of automatically assigning to terms of λ-calculus EAL formulas as types. This problem is proved to be decidable, and an algorithm is showed, building, for every λ-term, either a negative answer or a finite set of type schemata, from which all and only its typings can be derived, through suitable operations.
Paper partially supported by MIUR-cofin-2000 “Linear Logic and Beyond”,EC-TMR project “Linear Logic”,IST-2001-33477 DART Project,MIUR-cofin-2001 COMETA
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asperti, A., Coppola, P., Martini, S.: (Optimal) duplication is not elementary recursive. In: Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POLP-00), N.Y., ACM Press (2000) 96–107
Baillot, P.: Checking Polynomial Time Complexity with Types. In: Proc. of 2nd IFIP International Conference on Theoretical Computer Science (TCS 2002). Volume 223 of IFIP Conference Proceedings., Montréal, Québec, Canada (2002) 370–382
Baillot, P.: Type inference for polynomial time complexity via constraints on words. Prepublication LIPN Universite Paris Nord (2003)
Coppola, P., Martini, S.: Typing Lambda Terms in Elementary Logic with Linear Constraints. In Abramsky, S., ed.: Proc. of Typed Lambda Calculi and Applications, 5th International Conference, TLCA 2001. Volume 2044 of Lecture Notes in Computer Science., Springer (2001) 76–90
Curry, H.B.: Functionality in combinatory logic. In: Proc. Nat. Acad. Science USA. Volume 20. (1934) 584–590
Curry, H.B., Feys, R.: Combinatory Logic, Volume I. Studies in Logic and the Foundations of Mathematics. North-Holland, Amsterdam (1958)
Curry, H.B., Hindley, J.R., Seldin, J.P.: Combinatory Logic, Volume II. Studies in Logic and the Foundations of Mathematics. North-Holland, Amsterdam (1972)
Danos, V., Joinet, J.B., Schellinx, H.: On the linear decoration of intuitionistic derivations. In: Archive for Mathematical Logic. Volume 33. (1995) 387–412
Danos, V., Joinet, J.B.: Linear Logic and Elementary Time. ICC’99, to appear in Information & Computation (1999)
Girard, J.Y.: Light linear logic. Information and Computation 204 (1998) 143–175
Lamping, J.: An algorithm for optimal lambda calculus reduction. In ACM, ed.: POPL’ 90. Proceedings of the seventeenth annual ACM symposium on Principles of programming languages, January 17–19, 1990, San Francisco, CA, New York, NY, USA, ACM Press (1990) 16–30
Schellinx, H.: The Noble Art of Linear Decorating. PhD thesis, Institute for Logic, Language and Computation, University of Amsterdam (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Coppola, P., della Rocca, S.R. (2003). Principal Typing in Elementary Affine Logic. In: Hofmann, M. (eds) Typed Lambda Calculi and Applications. TLCA 2003. Lecture Notes in Computer Science, vol 2701. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44904-3_7
Download citation
DOI: https://doi.org/10.1007/3-540-44904-3_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40332-6
Online ISBN: 978-3-540-44904-1
eBook Packages: Springer Book Archive