|
Pro.Platz Programming language aspects of sublinear space complexity classes |
|
|
|
Pro.Platz Programming language aspects of sublinear space complexity classes |
|
This project is concerned with machine-independent, resource-free characterizations of small space complexity classes by use of logical and programming language concepts.
Next to theoretical insights into the nature of these classes, this yields methods for the automatic analysis of the runtime and storage usage of programs. Other applications are some specific optimizations that can be obtained from the complexity-theoretic analysis.
Characterizations like this have long been known for polynomial time (P) and larger classes. For smaller classes, defined by logarithmic storage space, only rudimentary approaches exist so far.
With respect to the aforementioned applications, these classes are particularly relevant in scenarios with strongly bounded resources, like peer-to-peer computing, embeddded systems or mobile code. Although the main emphasis will be on theoretical foundations, such applications will also be investigated.
The project is funded by the German Research Foundation (DFG) with one position for a research associate (BAT IIa).
Wiki Deutsche Version