Trace Theory has been motivated by the Theory of Petri Nets and the Theory of Automata and Formal Languages. Trace languages represent the behaviours of concurrent systems in the same way as formal languages represent the behaviours of sequential systems.

This theory received considerable attention in the following areas :

- Algebra and Combinatorics,

- Languages and Automata,

- Concurrency and Logic

More recently, it has been pointed out the interest of traces for modelling problems of code parallelization. A purpose of this meeting is to explore the use of Trace Theory in this direction presenting some recent developments.

****************** Programme ***************************************

-------------------------------------------------------------------

Thursday June 1 st, morning

Sala Lauree, DSI, via Comelico 39

-------------------------------------------------------------------

9:55: Opening

--------------------------------------------------------------------

10:00-11h : Invited talk

Heaps of pieces, trace monoids, Petri Nets and max-plus automata (Jean Mairesse)

--------------------------------------------------------------------

11:00 - 12,30

A survey on trace coding (Clelia De Felice)

Inclusion problem for unambiguous regular trace languages (Paolo Massazza)

-------------------------------------------------------------------

LUNCH

-------------------------------------------------------------------

-------------------------------------------------------------------

Thursday June 1 st, afternoon

Sala Conferenze, DEI, via Ponzio 34/5

-------------------------------------------------------------------

15:00 – 17:30

Trace Theory and code parallelization (Luca Breveglieri, Stefano Crespi Reghizzi, Marco Garatti)

Languages and partial commutations (Antonio Restivo, Giovanna Guaiana)

Parallel Algorithms for extimating the average height of traces (Beatrice Palano, Alberto Bertoni, Massimiliano Goldwurm)

-------------------------------------------------------------------

Friday June 2 nd

Sala Lauree, DSI, via Comelico 39

-------------------------------------------------------------------

-------------------------------------------------------------------

9:30 –10:30 : Invited talk

Anca Muscholl

-------------------------------------------------------------------

10:30 – 13

A calculus for automata with applications to model-checking and coordination languages

(Pierluigi Katis, Nicoletta Sabadini, Robert Walters)

Clique polynomials and trace monoids (Massimiliano Goldwurm, Massimo Santini)

Trace monoids represented by 2X2 integer matrices (Christian Choffrut)

The workshop is supported by :

DSI - Università degli Studi di Milano

DEI - Politecnico di Milano

CNR - Centro Studi Tecnologici, Informatica e Automazione, Milano

Progetto MURST "Modelli di calcolo innovativi: metodi sintattici e combinatori".