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.
Details
- Publication Date
- Jan 1, 2009
- Language
- English
- ISBN
- 9781409273134
- Category
- Computers & Technology
- Copyright
- All Rights Reserved - Standard Copyright License
- Contributors
- By (author): Stefan Schimanski
Specifications
- Pages
- 285
- Binding Type
- Paperback Perfect Bound
- Interior Color
- Black & White
- Dimensions
- A5 (5.83 x 8.27 in / 148 x 210 mm)