Preliminary Program


Session 1: 15:00 - 15:45

    [15:00] Invited Talk: The lambda-calculus in different scenarios
    Mariangiola Dezani-Ciancaglini, Torino

Session 2: 16:00 - 17:00

    [16:00] Concrete Syntax for Intuitionistic Light Affine Logic with Polymorphic Type Assignment
    L. Roversi, Marseille

    [16:20] A Type Assignment System for the Game Semantics
    P. Di Gianantonio, G. Franco, Udine, Udine

    [16:40] A Game Semantics Foundation for Logic Programming
    R. Di Cosmo, J.-V. Loddo, S. Nicolet, DMI-LIENS, DMI-LIENS, DMI-LIENS

Coffee Break

Session 3: 17:15 - 18:15

    [17:15] Tight Bounds on Broadcasting with Dynamic Faults
    G. De Marco, A. A. Rescigno, Salerno, Salerno

    [17:35] A New Modular Division Algorithm and Applications
    M.S. Sedjelmaci, C. Lavault, Paris-Nord, Paris-Nord

    [17:55] Fast Single Precision Evaluation of Sign of Determinants
    F. d'Amore, P. G. Franciosa, La Sapienza, La Sapienza


Session 1: 09:00 - 9:45

    [09:00] Invited Talk: Algorithmics of regularity and anomaly detection
    Alberto Apostolico, Padova & Purdue

Session 2: 10:00 - 11:00

    [10:00] From bandwidth k to pathwidth k
    A.Proskurowski, J.A.Telle, Oregon, Bergen

    [10:20] Maintaining dynamic graph properties deterministically
    M. Marzolla, Venezia

    [10:40] Rooted Spanning Trees with Small Weight and Average Length
    G. Frederickson, R. Solis-Oba, Purdue, Max Planck Institut

Coffee Break

Session 3: 11:15 - 12:35

    [11:15] A Symbolic Semantics for Abstract Model Checking
    F. Levi, Pisa

    [11:35] A Fixpoint-Based Axiom System for ACTL
    G. Lenzi, Bordeaux

    [11:55] Proof Systems with Cut Elimination for MTL^{leq_{Q}}
    F. Montagna, G. M. Pinna, E. B.P. Tiezzi, Siena, Siena, Siena

    [12:15] A Natural Deduction Style Proof System for Propositional mu-Calculus and its Formalization in Inductive Type Theories
    M. Miculan, Udine

Lunch Break

Session 4: 14:30 -15:15

    [14:30] Invited Talk:Ambient Decor
    Luca Cardelli, Cambridge

Session 5: 15:30 - 16:50

    [15:30] Implementing Tile Systems: some Examples from Process Calculi
    R. Bruni, J. Meseguer, U. Montanari, Pisa, SRI International, Pisa

    [15:50] Some Concurrency Models in a Categorical Framework
    C. Bodei, Pisa

    [16:10] Enabling and General Distributions in Stochastic Process Algebras
    C. Priami, Verona

    [16:30] Functional and Performance Modeling and Analysis of Token Ring using EMPA
    M. Bernardo, M. Bravetti, Bologna, Bologna

Coffee Break

Session 6: 17:05 - 17:45

    [17:05] Threshold Circuits for some Matrix Operations. Consequences on Regular and Probabilistic Languages
    C. Mereghetti, B. Palano, Milano, Milano

    [17:25] Q-ary Searching with Lies
    F. Cicalese, Salerno

18:00 Assembly of the Italian Chapter of EATCS


Session 1: 09:00 - 9:45

    [09:00] Invited Talk: Besides LRU, what else is there to say about paging?
    Amos Fiat, Tel Aviv

Session 2: 10:00 - 11:20

    [10:00] Quantum NP is Hard for PH
    S. Fenner, F. Green, S. Homer, R. Pruim, Southern Maine, Clark, Boston, Calvin

    [10:20] Downward Collapse from a Weaker Hypothesis
    E. Hemaspaandra, L. A. Hemaspaandra, H. Hempel, Le Moyne, Rochester, Jena

    [10:40] On the Polynomial Representation of Boolean Functions over GF(2)
    A. Bernasconi, Munchen

    [11:00] Spectral Techniques for Depth-3 Threshold Circuits
    G. Cattaneo, A. Leporati, G. Mauri, Milano, Milano, Milano

Coffee Break

Session 3: 11:35 - 12:35

    [11:35] New Constructions for Visual Cryptography
    C. Blundo, A. De Bonis, Salerno, Salerno

    [11:55] Languages for Description and Analysis of Authentication Protocols
    F. Martinelli, Siena

    [12:15] Using Entity Locations for the Analysis of Authentication Protocols
    R. Focardi, Venezia

Lunch Break

Session 4: 14:30 - 15:50

    [14:30] Analysis of Normal Logic Programs
    F.Fages, R.Gori, LIENS CNRS, Pisa

    [14:50] An Experiment in Domain Refinement: Type Domains and Type Representations for Logic Programs
    F. Spoto, Pisa

    [15:10] Call-Correct Specialisation of Logic Programs
    A. Bossi, S. Rossi, Venezia, Padova

Coffee Break

Session 5: 15:45 - 16:45

    [15:45] Factorizing Codes and Krasner Factorizations
    C. De Felice, R. Zizza, Salerno, Milano

    [16:05] Transition Diagram Systems and Normal Form Algorithms
    D. Giammarresi, D. Wood, Venezia, Hong Kong

    [16:25] On the Extension of Fine and Wilf's Periodicity Theorem to Linear Automata
    G. Melideo, C. Pasquarelli, S. Varricchio, L'Aquila, L'Aquila, L'Aquila

End of the Colloquium

Sponsored by:

The European Association of Theoretical Computer Science (EATCS)
Università di Pisa
Università of Salerno
Dipartimento di Informatica ed Applicazioni ``Renato M. Capocelli''
Italian National Council of Research (Comitato Nazionale per le Scienze Matematiche, GNIM-CNR, and Comitato Nazionale per le Scienze di Ingegneria e Architettura).

For comments or suggestions please write to