This thesis is about type systems which guarantee polynomial time complexity of typed programs. A type system is a tool to give a computer program an additional structure which makes sure that it satisfies certain properties. In this work type systems are introduced and mathematically analysed, which type only those algorithms which terminate after polynomially many execution steps in the size of the input. Polynomial time is an important complexity class for practical application because polynomial algorithms grow reasonable fast to be feasibly computable also for bigger inputs.
- ISBN10 1447616782
- ISBN13 9781447616788
- Publish Date 24 April 2012 (first published 30 March 2009)
- Publish Status Active
- Publish Country GB
- Imprint Lulu.com
- Format eBook (OEB)
- Language English