Programming with Alternation
|
Supervisor |
|
|
Suitable for |
Honour School of Mathematics and Computer Science, Part C
|
Abstract
Background: Alternation is a powerful computing paradigm involving nondeterminism. Algorithms for many problems are more easily described in terms of an alternating computations than in terms of sequential nondeterministic computations. AlterIt is known that alternating LOGSPACE is equal to PTIME.Principal goal of the project: To design a programming language (or extension of a procedural programming language) suited for computing with alternations, and write a compiler. The compiler will translate alternating programs into a sequential program in a language such as C++ or Java. An important part of this work will deal with issues of efficient storage management and runtime optimization.
Skills Needed: The project involves issues of programming language design, compiler construction, and theory of computation.