We believe Trace Theory offers great potential for modelling concurrent and parallel computation. In order to assess its current development, we contribute to the ESF Workshop on Developments and New Tracks in Trace Theory, Cremona, Italy, 9-11 October 2008.

Our work aims at finding new algorithms for program parallelization by exploiting theoretical properties of trace languages, a class of languages that suitably model the dependencies between code instructions.

In particular, for a subclass of “well structured” programs, we are able to efficiently decide whether a sequence of instructions is an admissible re-scheduling of a given execution. We are now investigating how to extend this result to a wider class of programs.