[Prev][Next][Index][Thread]
ICALP'97 - preliminary programme
-
To: types@dcs.gla.ac.uk
-
Subject: ICALP'97 - preliminary programme
-
From: busi@CS.UniBO.IT (Nadia Busi)
-
Date: Fri, 18 Apr 1997 15:47:31 +0200
-
Delivery-Date: Fri, 18 Apr 1997 08:53:13 -0500
*******************************************************
* *
* ICALP '97 *
* ========= *
* 24th International Colloquium on Automata, *
* Languages, and Programming *
* *
* Silver Jubilee of EATCS *
* *
* Bologna, Italy, July 7th - 11th, 1997 *
* *
*******************************************************
PRELIMINARY PROGRAMME
*******************************************************
This announcement and more information about the conference is available
per www under
http://www.cs.unibo.it/icalp97/
or by sending e-mail to icalp97@cs.unibo.it
Please address inquiries, registration form and hotel reservation form
to the Conference Office:
Italiana & Co. - ICALP'97
Via Altabella 3
I-40126 BOLOGNA (Italy)
Phone: + 39 51 228716
Fax: + 39 51 222881
Email: italiana@bo.nettuno.it
-------------------------------------------------------------------------------
GENERAL INFORMATION
^^^^^^^^^^^^^^^^^^^
The 24th annual meeting of the European Association for Theoretical Computer
Science (EATCS) will take place in Bologna, Italy, July 7-11 1997.
ICALP '97 comes in conjunction with the 25th anniversary of the foundation
of EATCS. To celebrate the SILVER JUBILEE, this edition of ICALP includes
several new events:
- Celebration of EATCS and of its founders (keynote speaker M. Nivat - Paris)
- Invited Lectures on major advances in theoretical computer science since
EATCS has been established:
R. Milner (Cambridge) M.O. Rabin (Jerusalem and Harvard)
C. Papadimitriou (Berkeley) D.S. Scott (Pittsburgh)
- Invited Lectures on the state of the art and new promising trends:
K.R. Apt (Amsterdam) K. Mehlhorn (Saarbruecken)
R.J. Lipton (Princeton) D. Perrin (Marne-la-Vallee)
- A panel on 'Funding Policies for Theoretical Computer Science' with
representatives from major research agencies and from the European Community.
- A number of Satellite Workshops, listed below, on theory and applications.
ICALP SATELLITE WORKSHOPS
^^^^^^^^^^^^^^^^^^^^^^^^^
- Workshop on New Trends in Semantics - Bologna (4-5 July) Organizers:
A.Asperti (Bologna), E.Moggi (Genova) and G.Rosolini (Genova).
Invited Speakers: S.Abramski (Edinburgh), V.Danos (Paris), A.Joyal
(Montreal), D.Sangiorgi (Sophia-Antipolis).
http://www.disi.unige.it/conferences/new-trends97/
- Second International ERCIM Workshop on Formal Methods in Industrial
Critical Systems - Cesena (4-5 July) - Organizers: S. Gnesi, D. Latella,
L. Simoncini (Pisa).
Invited Speakers: E.Brinksma (Twente), U.Herzog (Erlangen), R.Mazzeo
(Sasib Railways), G.Mongardi (Ansaldo Trasporti).
http://fdt.cnuce.cnr.it/~latella/FMICS/WS/Cesena97/workshop.html
- Second International Workshop on Advanced Intelligent Networks (AIN'97) -
Cesena (4-5 July) - Organizers: T. Margaria and B. Steffen (Passau).
Invited Speakers: P.Zave (AT&T), M.Decina (Milano), A.Limongiello
(Telecom Italia).
http://brahms.fmi.uni-passau.de/bs/organization/ain97/ain97.html
- Workshop on Approximation and Randomized Techniques in Computer Science
(Random) - Bologna (11-12 July) - Organizers: J. Rolim (Geneva) and
A. Clementi (Rome).
Invited Speakers: S.Arora (Princeton), P.Crescenzi (Rome), R.Impagliazzo
(San Diego), M.Karpinski (Bonn).
http://cuiwww.unige.ch/~random97
- Workshop on Recent Developments in Formal Languages - Bologna (11-12 July)
Organizer: S.Varricchio (L'Aquila), G.Pirillo (Firenze).
Invited Speaker: D. Perrin (Marne-la-Vallee).
http://univaq.it/~varricch/workshop.html
- Workshop on Algorithmic Aspects of Communication - Bologna (11-12 July) -
Organizers: M. Bonuccelli (Pisa) and A. Marchetti-Spaccamela (Rome).
http://www.di.unipi.it/~bonucce/AlAsCo.html
- Second International Workshop on Verification of Infinite State Systems
(Infinity) - Bologna (11-12 July) - Organizer: F.Moller (Uppsala).
http://www.csd.uu.se/~fm/infinity97cfp.html
-------------------------------------------------------------------------
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% CONFERENCE PROGRAMME %
% %
% ICALP '97 %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Sunday, July 6
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Registration: Aula Prodi, 18:30-20:30
Reception: Aula Prodi, 20:30-21:30
Monday, July 7
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Registration: Aula Absidale, 8:30- 9:15
Welcome address: 9:15- 9:30
9:30 Invited Lecture: Dana Scott (CMU, Pittsburgh)
(title to be announced)
10:30 An abstract data type for real numbers
P. Di Gianantonio
Coffee Break: 10:55 - 11:15
-------------------------------------------------------------------------
11:15 - 12:55 Parallel Sessions
A : Formal Languages I B : Computability
-------------------------------------------------------------------------
Enumerative sequences of leaves Recursive Computational Depth
in rational trees J.Lathrop, J. Lutz
F.Bassino, M.-P. Beal,
D. Perrin
A completion algorithm for codes Some bounds on the computational
with bounded synchronization delay power of Piecewise Constant
V. Bruyere Derivative systems
O. Bournez
The expressibility of languages Monadic simultaneous rigid
and relations by word equations E-unification and related problems
J.Karhumaeki, W.Plandowski, Y.Gurevich, A.Voronkov
F.Mignosi
Finite loops recognize exactly Computability on the Probability
the regular open languages Measures on the Borel Sets of the
M.Beaudry, F.Lemieux, D.Therien Unit Interval
K.Weihrauch
-------------------------------------------------------------------------
Lunch: 12:55 - 14:45
14:45 Invited Lecture: Michael O. Rabin (Hebrew U. of Jerusalem &
Harvard U.)
Randomization and the Correctness of Programs
15:45 Tilings and quasiperiodicity
B. Durand
Coffee Break: 16:10 - 16:30
-------------------------------------------------------------------------
16:30 - 18:10 Parallel Sessions
A : Computational Complexity B : Semantics I
-------------------------------------------------------------------------
Results on Resource-Bounded Measure Game Theoretic Analysis of
H.Buhrman, S.Fenner, L.Fortnow Call-by-value Computation
K.Honda, N.Yoshida
Randomization and nondeterminism On modular properties of higher
are incomparable for ordered order extensional lambda calculi
read-once branching programs R. Di Cosmo, N. Ghani
F. Ablayev
Checking Properties of Polynomials On Explicit Substitution and Names
B.Codenotti, F.Ergun, P.S. Gemmell, E. Ritter, V. de Paiva
S.Ravi Kumar
Exact Analysis of Dodgson Elections: On the Dynamics of Sharing Graphs
Lewis Carroll's 1876 Voting System A. Asperti, C. Laneve
is Complete for Parallel Access to NP
E.Hemaspaandra, L.Hemaspaandra,
J.Rothe
-------------------------------------------------------------------------
Tuesday, July 8
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
9:00 Invited Lecture: Robin Milner (U. Cambridge)
Graphical Calculi for Interaction
10:00 Bisimulation for probabilistic transition systems:
A coalgebraic approach
E. de Vink, J. Rutten
Coffee Break: 10:25 - 10:45
-------------------------------------------------------------------------
10:45 - 12:00 Parallel Sessions
A : Algorithms I B : Calculi for Concurrency I
-------------------------------------------------------------------------
Minimizing Diameters of Dynamic The name discipline of uniform
Trees receptiveness
S.Alstrup,J.Holm,K.de Lichtenberg, D. Sangiorgi
M.Thorup
Improving Spanning Trees by On confluence in the pi-calculus
Upgrading Nodes A. Philippou, D. Walker
S.Krumke, M.Marathe, H. Noltemeier,
R.Ravi,SS Ravi, R.Sundaram,
H.-C. Wirth
Dynamic algorithms for graphs of A proof theoretical approach to
bounded treewidth communication
T. Hagerup Y. Fu
Break: 12:00 - 12:10
-------------------------------------------------------------------------
12:10 - 13:00 Parallel Sessions
A : Formal Languages II B : Calculi for Concurrency II
-------------------------------------------------------------------------
Solving Trace Equations Using An Algebra-Based Method to
Lexicographical Normal Forms Associate Rewards with EMPA Terms
V.Diekert, Y.Matiyasevich, M. Bernardo
A. Muscholl
Star-free picture expressions are A Semantically Sound Actor
strictly weaker than 1st-order logic Translation
T. Wilke I. Mason, C. Talcott
-------------------------------------------------------------------------
Lunch: 13:00 - 14:45
-------------------------------------------------------------------------
14:45 - 16:00 Parallel Sessions
A : Algorithms II B : Logic and Verification
-------------------------------------------------------------------------
Periodic and Non-periodic Min-Max Computation Paths Logic: An
Equations Expressive, yet Elementary,
U.Schwiegelshohn, L.Thiele Process Logic
D.Harel, E.Singerman
Efficient Parallel Graph Algorithms Model Checking the Full Modal
For Coarse Grained Multicomputers Mu-Calculus for Infinite Sequential
and BSP Processes
E.Caceres, F.Dehne, A.Ferreira, O.Burkart, B.Steffen
P.Flocchini, I.Rieping, A.Roncato,
N.Santoro, S.Song
Upper bound on communication Symbolic Model Checking for
complexity of private information Probabilistic Processes
retrieval C.Baier, M.Kwiatkowska, M.Ryan,
A.Ambainis E.Clarke, V.Hartonas-Garmhausen
-------------------------------------------------------------------------
Coffee Break: 16:00 - 16:20
-------------------------------------------------------------------------
16:20 - 17:10 Parallel Sessions
A : Analysis of Algorithms B : Process Equivalences
-------------------------------------------------------------------------
On the concentration of the height Distributed Processes and Location
of binary search trees Failures
J.M. Robson J.Riely, M.Hennessy
An improved master theorem for Basic Observables for Processes
divide-and-conquer recurrences M.Boreale, R.De Nicola, R.Pugliese
S. Roura
-------------------------------------------------------------------------
Break: 17:10 - 17:15
17:15 - 18:15 Panel:
Funding Policies for Theoretical Computer Science
(with the participation of G.Metakides, DG III-EU)
-------------------------------------------------------------------------
Wednesday, July 9
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
9:00 - 11:30 Excursion: Guided tour to the city of Bologna
11:30 - 12:30 Laurea Honoris Causa in Computer Science tributed to
Robin Milner and Maurice Nivat by the University
of Bologna
Lunch: 12:30 - 14:45
14:45 - 15:45 Invited Lecture: Christos Papadimitriou (Berkeley)
NP-completeness: A Retrospective
15:45 - 16:10 Worst-case hardness suffices for derandomization: a new
method for hardness-randomness trade-offs
A. Andreev, A. Clementi, J. Rolim
Coffee Break: 16:10 - 16:30
-------------------------------------------------------------------------
16:30 - 18:10 Parallel Sessions
A : Routing Algorithms B : Petri Nets and Process Theory
-------------------------------------------------------------------------
Constrained Bipartite Edge Coloring Efficiency of Asynchronous Systems
with Applications to Wavelength and Read Arcs in Petri Nets
Routing W.Vogler
C.Kaklamanis,G.Persiano,T.Erlebach,
K.Jansen
Colouring Paths in Directed Bisimulation equivalence is
Symmetric Trees with Applications decidable for one-counter processes
to WDM Routing P.Jancar
L.Gargano, P.Hell, S.Perennes
On-line Routing in All-Optical Symbolic Reachability Analysis of
Networks FIFO Channel Systems with Nonregular
Y.Bartal, S.Leonardi Sets of Configurations
A.Bouajjani, P.Habermehl
A Complete Characterization of the Axiomatizations for the Perpetual
Path Layout Construction Problem for Loop
ATM Networks with Given Hop Count W.Fokkink
and Load
T.Eilam, M.Flammini, S.Zaks
-------------------------------------------------------------------------
Break: 18:10 - 18:20
18:20 - 18:45 Goedel Prize
18:45 - 19:30 EATCS General Assembly
-------------------------------------------------------------------------
Thursday, July 10
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
9:00 Invited Lecture: Kurt Mehlhorn and Stefan Naeher
(Max-Planck Institut, Saarbruecken)
The LEDA Platform of Combinatorial and
Geometric Computing
10:00 Maintaining Minimum Spanning Trees in Dynamic Graphs
M. Rauch Henzinger, V. King
Coffee Break: 10:25 - 10:45
-------------------------------------------------------------------------
10:45 - 12:00 Parallel Sessions
A : Algorithms III B : Rewriting
-------------------------------------------------------------------------
Efficient Splitting and Merging The Word Matching Problem is
Algorithms for Order Decomposable Undecidable for Finite Special
Problems String-Rewriting Systems that
R.Grossi, G.F.Italiano are Confluent
P.Narendran, F.Otto
Efficient Array Partitioning The Geometry of Orthogonal
S.Khanna, S.Muthukrishnan, S.Skiena Reduction Spaces
Z.Khasidashvili, J.Glauert
Constructive Linear Time Algorithms The Theory of Vaccines
for Branchwidth M.Marchiori
H.Bodlaender, D.Thilikos
Break: 12:00 - 12:10
-------------------------------------------------------------------------
12:10 - 13:00 Parallel Sessions
A : Formal Languages III B : Cryptography
-------------------------------------------------------------------------
On recognizable and rational formal On Characterization of Escrow
power series in partially commuting Encryption Schemes
variables Y.Frankel, M.Yung
M.Droste, P.Gastin
On a conjecture of J. Shallit Randomness-Efficient Non-
J.Cassaigne Interactive Zero-Knowledge
A.De Santis, G.Di Crescenzo,
G.Persiano
-------------------------------------------------------------------------
Lunch: 13:00 - 14:45
14:45 Invited Lecture: Dominique Perrin and Olivier Carton
(U. de Marne-la-Vallee)
Chains and Superchains in Finite Automata
15:45 The Equivalence Problem for Deterministic Pushdown
Automata is Decidable
G. Senizergues
Coffee Break: 16:10 - 16:30
-------------------------------------------------------------------------
16:30 - 18:10 Parallel Sessions
A : Algorithms IV B : Semantics II and Automata
-------------------------------------------------------------------------
Approximation results for the Refining and Compressing Abstract
optimum cost partition problem Domains
K.Jansen R.Giacobazzi, F.Ranzato
The Minimum Color Sum of Bipartite Labelled Reductions, Runtime
Graphs Errors, and Operational Subsumption
A.BarNoy, G.Kortsarz L.Dami
A Primal-Dual Approach to A Complete and Efficiently
Approximation of Node-Deletion Computable Topological
Problems for Matroidal Properties Classification of D-dimensional
T.Fujito Linear Cellular Automata over Z_m
G.Manzini, L.Margara
Independent sets in asteroidal Recognizability Equals Definability
triple-free graphs for Partial k-Paths
H.Broersma, T.Kloks, D.Kratsch, V. Kabanets
H.Mueller
-------------------------------------------------------------------------
18:10 - 18:40 Celebration of the Silver Jubilee of the EATCS
Keynote speaker: Maurice Nivat (Paris 7)
Towards a History of Automata: Why Were They Introduced?
What Are They Good for?
20:30 Banquet
-------------------------------------------------------------------------
Friday, July 11
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
9:00 Invited Lecture: Krzystof R. Apt (CWI, Amsterdam)
Constraint Programming and the
'Computation as Deduction' Paradigm
10:00 Discrete-time control for rectangular hybrid automata
Thomas A. Henzinger, Peter W. Kopke
Coffee Break: 10:25 - 10:45
10:45 Invited Lecture: Richard J. Lipton (Princeton Univ.)
Using DNA to Compute
Break: 11:45 - 12:00
-------------------------------------------------------------------------
12:00 - 12:50 Parallel Sessions
A : Biocomputing B : Logic Programming
-------------------------------------------------------------------------
Molecular Computing, Bounded Termination of Constraint Logic
Nondeterminism, and Efficient Programs
Recursion
R.Beigel, B.Fu S.Ruggieri
Constructing Big Trees from Short The expressive power of unique
Sequences total stable model semantics
P.Erdos, M.Steel, L.Szekely, F.Buccafurri, S.Greco, D.Sacca'
T.Warnow
End of ICALP'97
-------------------------------------------------------------------------
RELATED CONFERENCES
^^^^^^^^^^^^^^^^^^^
ICALP'97 will be preceded by LICS'97 and CONCUR'97, which will be
held in Warsaw, Poland, the week before. For more details see
http://www.bell-labs.com/topic/conferences/lics/
http://www.ipipan.waw.pl/conferences/concur97/
Warsaw is easily connected to Bologna via Vienna, Frankfurt, Munich,
Rome, Paris, Bruxelles, Amsterdam, London and others.
Further information for participants will be sent in a next mail and may
be found per www.