hal-00684026, version 1

Complexity Information Flow in a Multi-threaded Imperative Language

Jean-Yves Marion ¹, Romain Péchoux (, ) ¹

(2012)

• 1:  CARTE (INRIA Nancy - Grand Est / LORIA)
• 
  CNRS : UMR7503 – INRIA – Université de Lorraine France

Bibliographic reference

• Type of document: Research reports
• Domain: Computer Science/Computational Complexity
• Title: Complexity Information Flow in a Multi-threaded Imperative Language
• Abstract: 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.
• ACM Classification: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.3: Complexity Measures and Classes/F.1.3.1: Machine-independent complexity
• Full text language: English
• Report type: Research Report
• Page number: 16
• Publication date: 2012-03-01
• Keywords: Ptime characterization – ICC – tiering – non-interference – imperative language

Attached file list to this document: 

• hal-00684026, version 1
• http://hal.inria.fr/hal-00684026
• oai:hal.inria.fr:hal-00684026
• From: Romain Péchoux <>
• Submitted on: Friday, 30 March 2012 13:59:44
• Updated on: Friday, 30 March 2012 20:13:29