Kalmar, Linear Space, and P J. Otto Department of Mathematics McGill University otto@math.mcgill.ca August 12, 1993 is available by anonymous ftp from triples.math.mcgill.ca. It is in uuencoded compressed postscript in pub/otto/0-k-ls-p.uu. Thus ftp ftp> open triples.math.mcgill.ca ftp> Name (...): anonymous ... Guest login ok, send e-mail address as password. Password: ftp> cd pub ftp> cd otto ftp> get 0-k-ls-p.uu ftp> quit uudecode 0-k-ls-p.uu uncompress 0-k-ls-p.ps.Z We use 2-simplices to cut down the primitive recursive functions to the Kalmar elementary functions, and 1-simplices to cut down the primitive recursive functions to the functions of complexities linear space and P time. This translates work of [Leivant Marion], [Bellantoni], and [Bellantoni Cook]. As 2-simplices are less degenerate than 1-simplices, we first consider Kalmar elementary. Then, successively modifying characterizations, we consider linear space and P time. Remarks. 1. Kalmar elementary and linear space are levels 3 and 2 of the Grzegorczyk Hierarchy. E.g. see [Rose]. 2. The characterizations can be viewed as programming languages whose typing guarantees, without explicit bounds checking, that programs represent precisely the functions of the complexity class. Most of the category theory we need is in [Barr Wells]. For the little that we need of 2-categories, e.g. see [Kelly Street], [Makkai Pare]. This paper revises and expands the April 18, 1993 paper `Kalmar Elementary and 2-Simplices'. In particular, besides minor changes and corrections, 1. Linear time is omitted, as the characterization I had translated may need some repair. 2. Machine based soundness and completeness proofs for the linear space and P time characterizations are added. The machine based proofs unfold [Ritchie], [Cobham] from the proofs of [Bellantoni], [Bellantoni Cook] and make this paper largely self contained. [Bloch] has related work on machines. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++