Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

ICALP 96: Early Registration

2 views

Skip to first unread message

ICALP96 Rolf Wanka

unread,

May 16, 1996, 3:00:00 AM5/16/96

*********************************************************************
********** Deadline for early registration: May 15, 1996 **********
*********************************************************************

===============================================================================

CALL FOR PARTICIPATION AND PROGRAM
23rd INTERNATIONAL COLLOQUIUM ON AUTOMATA, LANGUAGES AND PROGRAMMING

ICALP'96

JULY 8 - JULY 12, 1996
Paderborn, Germany

*******************************************************************************
*******************************************************************************

This and further information is available from the ICALP'96 www server

************** http://www.uni-paderborn.de/~icalp96/ ***********************

*******************************************************************************
*******************************************************************************

PROGRAM COMMITTEE:
===============================================================================

J. Balcazar, Barcelona B. Monien, Paderborn (Co-Chairman)
J. Berstel, Paris I. Munro, Waterloo
R. Freivalds, Riga L. Pacholski, Wroclaw
Z. Galil, New York A. Pnueli, Rehovot
J. Karhumaeki, Turku A. Rosenberg, Amherst
R. Kemp, Frankfurt D. Sannella, Edinburgh
W. Maass, Graz S. Skyum, Aarhus
A. Marchetti-Spaccamela, Roma P. Spirakis, Patras
J. Matousek, Praha P. Vitanyi, Amsterdam
F. Meyer auf der Heide, Paderborn (Co-Chairman)

INVITED SPEAKERS:
===============================================================================

-- H. Ganzinger, Saarbruecken
-- M. Latteux, Lille and V. Bruyere, Mons
-- M. Rabin, Jerusalem and Cambridge
-- A. Ranade, Berkeley and Bombay
-- A. Razborov, Moscow

PROGRAM:
===============================================================================

MONDAY, JULY 8, 1996
********************

8:45 Opening

9:00 Invited Lecture:
"Saturation-Based Theorem Proving"
H. Ganzinger, (Saarbruecken, Germany)

SESSION 1 -- PROCESS THEORY I
Chair: Burkhard Monien (Paderborn, Germany)

9:50 "Algebraic Characterizations of Decorated Trace Equivalences over
Tree-like Structures"
X. J. Chen, R. De Nicola (Roma, Italy)

10:15 "Fast Asynchronous Systems in Dense Time"
L. Jenner, W. Vogler (Augsburg, Germany)

10:40 BREAK

SESSION 2 -- FAIRNESS, DOMINATION, AND THE MU-CALCULUS
Chair: Amir Pnueli (Rehovot, Israel)

11:00 "A Hierarchy Theorem for the MU-Calculus"
G. Lenzi (Pisa, Italy)

11:25 "An Effective Tableau System for the Linear Time MU-Calculus"
J. Bradfield (Edinburgh, United Kingdom),
J. Esparza, A. Mader (Muenchen, Germany)

11:50 "Characterizing Fairness Implementability for Multiparty Interaction"
Y.-J. Joung (Taipei, Taiwan)

12:15 "Termination of Context-Sensitive Rewriting by Rewriting"
S. Lucas (Valencia, Spain)

12:40 LUNCH

SESSION 3 -- LOGIC AND ALGEBRA
Chair: Leszek Pacholski (Wroclaw, Poland)

14:15 "A Complete Gentzen-style Axiomatization for Set Constraints"
A. Cheng, D. Kozen (Cornell, USA)

14:40 "Fatal Errors in Conditional Expressions"
M. Billaud (Bordeaux, France)

15:05 "Different Types of Arrow Between Logical Frameworks"
T. Mossakowski (Bremen, Germany)

15:30 "Effective Models of Polymorphism, Subtyping and Recursion"
J. Mitchell (Stanford, USA),
R. Viswanathan (Cambridge, United Kingdom)

15:55 BREAK

SESSION 4 -- LANGUAGES AND PROCESSES
Chair: Don Sanella (Edinburgh, United Kingdom)

16:20 "Regularity of All Context-free Processes is Decidable"
D. J. B. Bosscher, W. O. D. Griffioen (Amsterdam, The Netherlands)

16:45 "On Infinite Transition Graphs Having a Decidable Monadic Theory"
D. Caucal (Rennes, France)

17:10 "Semi-groups Acting on Context-free Graphs"
G. Senizergues (Bordeaux, France)

17:35 "Hard Sets Method and Semilinear Reservoir Method with Applications"
L. P. Lisovik (Kiev, Ukraine)

18:00 END OF SESSION

19:00 Guided Walk through Paderborn

TUESDAY, JULY 9, 1996
*********************

9:00 Invited Lecture:
"Bandwidth-efficient Parallel Computation"
Abhiram Ranade (Berkeley, USA, and Bombay, India)

SESSION 5 -- ALGEBRAIC COMPLEXITY
Chair: Rainer Kemp (Frankfurt, Germany)

9:50 "Random Polynomials and Polynomial Factorization"
Ph. Flajolet, X. Gourdon (LeChesnay, France)
D. Panario (Toronto, Canada)

10:15 "Optimal Groebner Base Algorithms for Binomial Ideals"
U. Koppenhagen and E. W. Mayr (Muenchen, Germany)

10:40 BREAK

SESSION 6 -- GRAPH ALGORITHMS
Chair: Sven Skyum (Aarhus, Denmark)

11:00 "Minimum Fill-in of Circle and Circular-arc Graphs"
T. Kloks (Eindhoven, The Netherlands), D. Kratsch (Jena, Germany),
C. K. Wong (Hong Kong)

11:25 "Practical Approximation Schemes for Maximum Induced-Subgraph Problems
on K_{3,3}-free or K_5-free Graphs"
Z. Z. Chen (Tokyo, Japan)

11:50 "Searching a Fixed Graph"
E. Koutsoupias (Los Angeles, USA), Ch. Papadimitriou (San Diego,
USA), M. Yannakakis (Murray Hill, USA)

12:15 "Improved Sampling with Applications to Dynamic Graph Algorithms"
M. Rauch Henzinger (Cornell, USA), M. Thorup (Copenhagen, Denmark)

12:40 LUNCH

SESSION 7 -- AUTOMATA
Chair: Juhani Karhumaki (Turku, Finland)

14:15 "The Expressive Power of Existential First Order Sentences of Buechi's
Sequential Calculus"
J.-E. Pin (Paris, France)

14:40 "Fixpoints for Rabin Tree Automata Make Complementation Easy"
R. Kaivola (Edinburgh, United Kingdom)

15:05 "New Upper Bounds to the Limitedness of Distance Automata"
K. Hashiguchi (Okayama, Japan)

15:30 "Recognizing Regular Expressions by Means of Dataflow Networks"
P. Raymond (Montbonnot-St. Martin, France)

15:55 BREAK

SESSION 8 -- COMPLEXITY THEORY
Chair: Paul Vitanyi (Amsterdam, The Netherlands)

16:20 "On the Power of Randomized Branching Programs"
F. Ablayev (Kazan, Russia), M. Karpinski (Bonn, Germany)

16:45 "Hitting sets Derandomize BPP"
A. E. Andreev (Moscow, Russia), A. E. Clementi (Roma, Italy),
J.D.P. Rolim (Geneva, Switzerland)

17:10 "On Type-2 Probabilistic Quantifiers"
R. Book (Santa Barbara, USA),
H. Vollmer, K. Wagner (Wuerzburg, Germany)

17:35 "Speeding-up Single-Tape Nondeterministic Computations by Single
Alternation, with Separation Results"
J. Wiedermann (Prague, Czech Republic)

18:00 END OF SESSION

18:15 General Assembly of the EATCS

WEDNESDAY, JULY 10, 1996
************************

9:00 Invited Lecture:
"Variable-length Maximal Codes"
Michel Latteux (Lille, France), Veronique Bruyere (Mons, Belgium)

SESSION 9 -- COMBINATORICS ON WORDS
Chair: Jean Berstel (Paris, France)

9:50 "On \omega-Generators and Codes"
S. Julia (Sophia Antipolis, France)

10:15 "On Standard Sturmian Morphisms"
A. de Luca (Roma, Italy)

10:40 BREAK

SESSION 10 -- ALGORITHMS I
Chair: Ian Munro (Waterloo, Canada)

11:00 "Constructions and Bounds for Visual Cryptography"
G. Ateniese, C. Blundo, A. De Santis (Salerno, Italy),
D. R. Stinson (Lincoln, USA)

11:25 "On Capital Investment"
Y. Azar (Tel Aviv, Israel), Y. Bartal (Berkeley, USA),
E. Feuerstein (Buenos Aires, Argentina), A. Fiat (Tel Aviv, Israel),
St. Leonardi (Roma, Italy), A. Rosen (Toronto, Canada)

11:50 LUNCH

13:00 EXCURSION TO CORVEY CASTLE
Visit of the Castle Library at the Principality of Corvey

19:30 CONFERENCE DINNER
at the Buergerhaus "Im Schlosspark", Schloss Neuhaus

THURSDAY, JULY 11, 1996
***********************

9:00 Invited Lecture:
"Lower Bounds for Propositional Proofs and Independence Results in
Bounded Arithmetics"
Alexander Razborov (Moscow, Russia)

SESSION 11 -- LOWER BOUNDS
Chair: Rusins Freivalds (Riga, Latvia)

9:50 "Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No
Multiplication"
P. B. Miltersen (Toronto, Canada)

10:15 "Lower Bounds for Row Minima Searching"
P. G. Bradford, K. Reinert (Saarbruecken, Germany)

10:40 BREAK

SESSION 12 -- PROCESS THEORY II
Chair: Harald Ganzinger (Saarbruecken, Germany)

11:00 "On the Complexity of Relational Problems for Finite State Processes"
S.K. Shukla, H.B. Hunt, D.J. Rosenkrantz, R.E. Stearns (Albany, USA)

11:25 "Deciding Finiteness of Petri Nets Up To Bisimulation"
P. Jancar (Ostrava, Czech Republic), J. Esparza (Muenchen, Germany)

11:50 "Mobile Processes with a Distributed Environment"
C. Bodei, P. Degano, C. Priami (Pisa, Italy)

12:15 "The Meaning of Negative Premises in Transition System Specifications II"
R.J. van Glabbeek (Stanford, USA)

12:40 LUNCH

SESSION 13 -- DATA STRUCTURES
Chair: Paul Spirakis (Patras, Greece)

14:15 "Average Case Analyses of List Update Algorithms, with Applications to
Data Compression"
S. Albers (Saarbruecken, Germany), M. Mitzenmacher (Berkeley, USA)

14:40 "Self-organizing Data Structures with Dependent Accesses"
F. Schulz, E. Schoemer (Saarbruecken, Germany)

15:05 "Lopsided Trees: Analyses, Algorithms and Applications"
V. S.-N. Choi, M. Golin (Hong Kong)

15:30 "Optimal Logarithmic Time Randomized Suffix Tree Construction"
M. Farach (Rutgers, USA), S. Muthukrishnan (Warwick, United Kingdom)

15:55 BREAK

SESSION 14 -- PARALLEL ALGORITHMS
Chair: Arnold Rosenberg (Amherst, USA)

16:20 "Improved Parallel Approximation of a Class of Integer Programming
Programming Problems"
N. Alon (Tel Aviv, Israel), A. Srinivasan (Singapore)

16:45 "Efficient Collective Communication in Optical Networks"
J.C. Bermond, S. Perennes (Sophia Antipolis, France),
L. Gargano, A.A. Rescigno, U. Vaccaro (Salerno, Italy)

17:10 "Shared-Memory Simulations on a Faulty-Memory DMM"
B. S. Chlebus (Warszawa, Poland), A. Gambin (Dortmund, Germany),
P. Indyk (Stanford, USA)

17:35 "Fast Deterministic Backtrack Search"
K. T. Herley (Cork, Ireland),
A. Pietracaprina, G. Pucci (Padova, Italy)

18:00 END OF SESSION

19:00 Reception by the Mayor of Paderborn

FRIDAY, JULY 12, 1996
***********************

9:00 Invited Lecture:
"Parallel Computing, From Theory to Practice"
Michael Rabin (Jerusalem, Israel and Harvard, USA)

SESSION 15 -- DISTRIBUTED SYSTEMS
Chair: Friedhelm Meyer auf der Heide (Paderborn, Germany)

9:50 "Agent Rendezvous: A Dynamic Symmetry-Breaking Problem"
X. Yu (Columbia, USA), M. Yung (Watson Research Center, USA)

10:15 "Efficient Asynchronous Consensus with the Value-Oblivious Adversary
Scheduler"
Y. Aumann, M.A. Bender (Harvard, USA)

10:40 BREAK

SESSION 16 -- ALGORITHMS II
Chair: Alberto Marchetti-Spaccamela (Roma, Italy)

11:00 "A Formal Framework for Evaluating Heuristic Programs"
L. Cowen (Baltimore, USA), J. Feigenbaum (Murray Hill, USA),
S. Kannan (Philadelphia, USA)

11:25 "Improved Scheduling Algorithms for Minsum Criteria"
S. Chakrabarti (Berkeley, USA), C. Phillips (Albuquerque, USA),
A. Schulz (Berlin, Germany), D.B. Shmoys (Cornell, USA),
C. Stein (Hanover, USA), J. Wein (Brooklyn, USA)

11:50 "On the Complexity of String Folding"
M. Paterson (Warwick, United Kingdom),
T. Przytycka (Odense, Denmark)

12:15 "A Polynomial-Time Algorithm for Near-Perfect Phylogeny"
D. Fernandez-Baca (Ames, USA), J. Lagergren (Stockholm, Sweden)

12:40 LUNCH

END OF ICALP'96

===============================================================================
GENERAL INFORMATION
===============================================================================

LOCATION/CONFERENCE SITE:
===============================================================================

All lectures will be given in the Conference Hall of the "Heinz Nixdorf
MuseumsForum", Fuerstenallee 7, 33102 Paderborn.

REGISTRATION/RECEPTION:
===============================================================================
There will be a reception for all registrants from 6.00 pm to 9.00 pm on
Sunday 7 at the Paderborn University, Building F, Fuerstenallee 11. This
building is located next to the conference site.

TRAVEL:
===============================================================================

There are several ways to reach Paderborn. The airport of Paderborn/Lippstadt
offers various connections to international airports (e.g. Amsterdam, London,
Paris). Taxis (cost about 50 DM) and regular busses are available from the
airport to the city (25 km). The nearest international airports are Duesseldorf
(180 km), Hannover (160 km) and Frankfurt (300 km).

There are good train connections from all these locations and other cities.

Highway Connection: A33 - exit Paderborn-Zentrum.

The conference site, Fuerstenallee 7, has regular connections with bus no. 11
(final destination: "Thuner Siedlung"; exit at bus stop: "Hopfenweg") from the
city center as well as from the railway station.

CLIMATE:
===============================================================================

Daytime temperatures in July are expected to be around 22 degrees Celsius,
nighttime temperatures around 15 degrees Celsius.

Sunshine is expected with smaller rain showers once in a while. The conference
rooms are fully air-conditioned.

ACCOMMODATION:
===============================================================================

The room capacity of hotels in the center of Paderborn, and therefore closely
to the conference site, is limited. The organizing team highly recommends your
booking as soon as possible.

!!! Please use the accommodation & registration form available from the !!!
ICALP'96 www-page at http://uni-paderborn.de/~icalp96/ or the combined form
at the end of this call or contact the organizing team.

Attention:
A hotel reservation, applied after June, 10 1996, cannot be guaranteed.

REGISTRATION FEE:
===============================================================================

Registration by May 15 after May 15
------------------------------------------------------
Member of EATCS 360 DM 410 DM
Non-member 400 DM 450 DM
Student * 240 DM 290 DM
Accompanying Person 120 DM 170 DM

* certification of full-time student status has to be included

The registration fee covers:

member/ student accompanying
non-member person
---------------------------------------------------------
Receptions ++ ++ ++
Excursion ++ ++ ++
Guided Walk ++ ++ ++ ++ included
Lunches, Refreshments ++ ++ -- -- not included
Conference Dinner ++ -- ++
Proceedings ++ -- --
1 year EATCS membership ++ -- --

The registration fee has to be paid either by bank transfer to the account
(make sure that all intermediate bank charges are covered by your payment):

Paderborn University
Purpose: ICALP'96
Sparkasse Paderborn
Account No.: 16107542
Bank Code: 472 501 01

or by a cheque (currency: German Mark (DM), Eurocheque preferred) payable to
Prof. Dr. B. Monien and send it to Dr. Walter Unger, Paderborn University,
Dept. of Computer Science, Fuerstenallee 11, D-33102 Paderborn, Germany

CANCELLATION:
===============================================================================

In the case of cancellation another participant can be named without any costs.
Otherwise an arrangement fee of 75.- DM has to be paid. No refund will be made
to those canceling their registration after June 10.

ACCOMPANYING PERSON PROGRAM:
===============================================================================

In addition to the receptions, excursion and conference dinner the organizing
team plans an interesting program for all accompanying persons during the
talks.

Tour A Visit of Detmold (a nice little town with good shopping areas), open
air museum, castle, organ recital

Tour B Sight-seeing Westphalia/Lippe: Schieder-Schwalenberg, Hameln and others.

Tour C Visiting Kassel (famous castle and garden)

All accompanying persons who are registered together with a conference parti-
cipant will receive detailed information (including cost estimates for these
additional activities), other interested persons will receive further informa-
tion on request.

EVENTS:
===============================================================================

Sunday, July 7 Reception at the Paderborn University, Building F,
18:00 - 21:00 Fuerstenallee 11. This building is located next to the
conference site.

Monday, July 8 Guided walk through Paderborn
19:00

Tuesday, July 9 EATCS General Assembly
18:15 (at the conference site)

Wednesday, July 10 Excursion to Corvey. Visit of the Castle Library at the
Excursion 13:00 Principality of Corvey with its over 70.000 books and
writs.

Conference Dinner at the Buergerhaus "Im Schlosspark" in Schloss Neuhaus
19:30

Thursday, July 11 Reception by the Mayor of Paderborn in the City Hall
19:00

SPONSORS:
===============================================================================

-- DFG - Deutsche Forschungsgemeinschaft
-- Paderborn University
-- Stadt Paderborn

PROCEEDINGS:
===============================================================================

Conference Proceedings are published by Springer-Verlag in the series "Lecture
Notes in Computer Science" and will be distributed at the conference.

ORGANIZING COMMITTEE:
===============================================================================

Bernard Bauer Christian Scheideler
Birgit Farr Willy-B. Strothmann
Erich Koester Walter Unger
Friedhelm Meyer auf der Heide Rolf Wanka
Burkhard Monien

FURTHER INFORMATION:
===============================================================================

You will find all forms and a lot of additional information on the ICALP'96
www-page
http://uni-paderborn.de/~icalp96/

or contact the organizing team via:

email ica...@uni-paderborn.de
phone +49 5251 60-6296
fax +49 5251 60-6297

===============================================================================
===============================================================================
===============================================================================
ICALP'96 ACCOMMODATION & REGISTRATION FORM
===============================================================================
===============================================================================
===============================================================================

Please, fill in this form with typewriter or block letters, very legible and

send it to Dr. Walter Unger
Paderborn University
Dept. of Computer Science
Fuerstenallee 11
D-33102 Paderborn

Surname: __________________________

First name: ________________________ Title: ___________________________

Affiliation: ______________________________________________________________

Address: ______________________________________________________________

______________________________________________________________

______________________ Country: ___________________________

______________________ Phone: ___________________________

Email: ______________________ Fax: ___________________________

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

Accommodation Form: If you fill in the accommodation form, the organizing team
******************* will forward it directly to the Verkehrsverein Paderborn,
Marienplatz 2a, D-33098 Paderborn, Germany
Phone: +49 5251 26461, Fax: +49 5251 22884

Attention: A hotel reservation, applied after June 10th,
cannot be guaranteed.

Arrival Date: ___________________ Time: __________________

Departure Date:__________________ Time: __________________

Please reserve: [ ] -- mark appropriately

A B C
from 130.- DM 80.- DM to 130.- DM up to 80.- DM
-------------------------------------------------------------------------------

___ single room(s) [ ] [ ] [ ]

___ double room(s) [ ] [ ] [ ]

(Price per room and day)

If no room(s) are available in selected category

a) I herewith make a reservation of ___ room(s) of category ___

b) I herewith make a double room of category ___ at my exclusive disposal

___________________________________________________________
date and signature

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

Registration Form: Complete one for each participant.
****************** [ ] -- mark appropriately

my conference fee is:

Registration by May 15 after May 15
----------------------------------------------------------
Member of EATCS [ ] 360 DM [ ] 410 DM
Non-member [ ] 400 DM [ ] 450 DM
Student * [ ] 240 DM [ ] 290 DM * certification of
full-time student
Accompanying Person [ ] 120 DM [ ] 170 DM status has to be
included
How many: ___
Give their name(s): ___________________________________________________________

Total fee DM: ___________

[ ] I have transferred the fee to the ICALP account (no. 16107542) at the
Sparkasse Paderborn (bank code 472 501 01)
(make sure that all intermediate bank charges are covered by your payment,
please enclose a copy of the receipt of your payment)

[ ] Cheque enclosed

___________________________________________________________
date and signature

0 new messages