Mathematical Structures in Computer Science (MSCS)

Joint Special Issue(s) devoted to

``The Difference between Concurrent and Sequential Computation''

and to selected papers from EXPRESS'00: 7th International Workshop on
Expressiveness in Concurrency

(Giuseppe Longo editor in chief, Luca Aceto and Björn Victor guest editors)

CALL FOR PAPERS

Computer Science has witnessed the emergence of a plethora of different logics, models and paradigms for the description of computation. Yet, the classic Church-Turing thesis may be seen as indicating that all models of general model of computation are equivalent. Alan Perlis referred to this as the "Turing tarpit": some of the most crucial distinctions in computing methodology, such as sequential versus parallel, determinate versus nondeterministic, local versus distributed disappear if all one sees in computation is pure symbol pushing. How can we express formally the difference between these models of computation?

This double issue of MSCS aims at addressing this fundamental question by focusing on the dichotomy between sequential and concurrent computation. In particular, on ways to capture formally that any translation from an expressive approach to concurrency to a formalism like that of Turing Machines would miss "what really matters". By way of example, in Physics, people know very well that non-Euclidean geometries can be "embedded" into the Euclidean one (and conversely), but they know that the equivalence, an interesting equicoeherence, misses what really matters, e.g. the geometric structure of physical (relativistic) space. Similarly, one can surely give an "isomorphism" (as sets) between the real line and the plane (or any finite dimensional space), but this misses all what matters in the notion of Cartesian space, e.g. the dimension (which is a topological invariant, not a set-theoretic one).

Are there theorems or rigorous arguments as to confirm the view that translating concurrency in sequential computation misses some important aspect of concurrency? Which is the peculiar role played by space (and time) in distributed, concurrent systems?

This special issue of MSCS is devoted to papers addressing this issue in a creative and novel way. Broad surveys on this topic are also welcome. In addition, if the quality of submitted papers warrants it, a companion issue of the journal will be devoted to selected papers from EXPRESS'00, the 7th International Workshop on Expressiveness in Concurrency.

Authors who plan to submit a paper should kindly inform one of the editors (as soon as possible and) not later than October 30, 2000. The deadline for submissions is January 15, 2001. All submitted papers will be refereed according to the MSCS refereeing process. Information on MSCS and EXPRESS may be found at the URLs http://uk.cambridge.org/journals/msc/ and http://www.docs.uu.se/~victor/Express/express00.shtml respectively.

Björn Victor