Complexity Information Flow in a Multi-threaded Imperative Language

Details Complexity Information Flow in a Multi-threaded Imperative Language Complexity Information Flow in a Multi-threaded Imperative Language

2012-03-30

arxiv.org/abs/1203.6878v1

Computer Science

Computational Complexity

Scientific paper

We propose a type system to analyze the time consumed by multi-threaded imperative programs with a shared global memory, which delineates a class of safe multi-threaded programs. We demonstrate that a safe multi-threaded program runs in polynomial time if (i) it is strongly terminating wrt a non-deterministic scheduling policy or (ii) it terminates wrt a deterministic and quiet scheduling policy. As a consequence, we also characterize the set of polynomial time functions. The type system presented is based on the fundamental notion of data tiering, which is central in implicit computational complexity. It regulates the information flow in a computation. This aspect is interesting in that the type system bears a resemblance to typed based information flow analysis and notions of non-interference. As far as we know, this is the first characterization by a type system of polynomial time multi-threaded programs.

Affiliated with

Also associated with

No associations

Rating

Complexity Information Flow in a Multi-threaded Imperative Language does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity Information Flow in a Multi-threaded Imperative Language, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity Information Flow in a Multi-threaded Imperative Language will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-65087