Patrick Baillot. Checking polynomial time complexity with types.
Foundations of Information Technology in the Era of Network and Mobile Computing (proceedings of TCS2002).
Several researchers have proposed programming languages with intrinsic complexity properties, for instance languages ensuring that all functions representable are PTIME without refering to an explicit time measure. This work follows the same approach.
By relegating the handling of the complexity property to the type system, the programming task becomes easier, since the programmer is freed from manually providing information needed for the complexity analysis. All well typed programs are PTIME.
But is the type system decidable? See section 4 for details!
More information can be found in the preprint Type inference for polynomial time complexity via constraints on words.
Posted to theory by Ehud Lamm on 2/20/03; 2:19:03 AM