tl@forseti.uni-paderborn.DE (Thomas Lengauer) (02/07/90)
AFCET GI
STACS 90, Rouen
7th Symposium on Theoretical Aspects of Computer Science
February 22-24, 1990
Palais des Congres
Place de la Cathedrale
Rouen, France
The Symposium on Theoretical Aspects of Computer Science is organized jointly
by the Special Interest Group for Applied Mathematics of AFCET (Association
Francaise pour la Cybernetique Economique et Technique) and the Special
Interest Group for Theoretical Computer Science of GI (Gesellschaft fuer
Informatik). It is alternatively held in France and in Germany (Paderborn in
1989, Bordeaux in 1988 etc. ...).
Program Committee
J. Beauquier (Orsay), C. Choffrut (Rouen, Chairman), P. Darondeau (Rennes), H.
Ehrig (W. Berlin), H. Jung (E. Berlin), T. Lengauer (Paderborn, Chairman), E.W.
Mayr (Frankfurt), F. Orejas (Barcelona), M.H. Overmars (Utrecht), A. Restivo
(Palermo), P. Schupp (Urbana), J.M. Steyaert (Palaiseau), K.W. Wagner
(Wuerzburg)
This symposium will include systems exhibitions.
Sponsored by
CNRS, Universite de Rouen, Conseil Regional de Haute Normandie
SCIENTIFIC PROGRAM
Thursday, February 22, 1990
Session 1: Complexity I (H. Jung, Chairman)
9.00 - 9.50 Invited lecture: The complexity of local optimization
M. Yannakakis (Murray Hill, USA)
10.15 - 10.45 Counting classes: thresholds, parity, mods and fewness
R. Beigel, J. Gill and U. Hertrampf (Yale, Stanford, USA &
Wuerzburg, W. Germany)
10.45 - 11.15 A note on the almost-everywhere hierarchy for nondeterministic
time
E. Allender, R. Beigel, U. Hertrampf and S. Homer (Wuerzburg,
W. Germany & New Brunswick, New Haven, Boston, USA)
11.15 - 11.45 Minimal pairs and complete problems
K. Ambos-Spies, S. Homer and R.I. Soare (Heidelberg, W.
Germany & Boston, Chicago, USA)
11.45 - 12.15 Hard promise problems non-uniform complexity
L. Longpre and A.L. Selman (Boston, USA)
Session 2: Computational Geometry (M.H. Overmars, Chairman)
14.00 - 14.30 Minimum vertex hulls for polyhedral domains
G. Das and D. Joseph (Wisconsin, USA)
14.30 - 15.00 On the construction of abstract Voronoi diagrams
K. Mehlhorn, St. Meiser and C.O. Dunlaing (Saarland, W.
Germany & Dublin, Ireland)
15.00 - 15.30 Approximation of convex figures by pairs of rectangles
O. Schwarzkopf, U. Fuchs, G. Rote and E. Welzl (Berlin, W.
Germany & Graz, Austria)
Session 3: Semantics (P. Darondeau, Chairman)
16.00 - 16.30 Towards a process semantics in the logic programming style
A. Corradini and U. Montanari (Pisa, Italy)
16.30 - 17.00 Relation-sorted algebraic specifications with built-in
coercers: Basic notions and results
H.-J. Kreowski and Z. Qian (Bremen, W. Germany)
17.00 - 17.30 Failures semantics based on interval semiwords is a congruence
for refinement
W. Vogler (Muenchen, W. Germany)
Friday, February 23, 1990
Session 4: Algorithms (J.M. Steyaert, Chairman)
9.00 - 9.50 Invited lecture: Combinatorial methods in computer science
G. Viennot (Bordeaux, France)
10.15 - 10.45 Nonblocking graphs: Greedy algorithms to compute disjoint
paths
A. Schwill (Oldenburg, W. Germany)
10.45 - 11.15 Updating almost complete trees or one level makes all the
difference
T. Lai and D. Wood (Waterloo, Canada)
11.15 - 11.45 Sorting the sums (xi + yj) in O(n2) comparisons
J.-L. Lambert (Orsay, France)
11.45 - 12.15 Parallel computations on strings and arrays
M. Crochemore and W. Rytter (Paris, France & Warsaw, Poland)
Session 5: Complexity II (H. Ehrig, Chairman)
14.00 - 14.30 Playing games of incomplete information
J. Cai, A. Condon and R.J. Lipton (Princeton, Wisconsin, USA)
14.30 - 15.00 Efficient checking of computations
R.J. Lipton (Princeton, USA)
15.00 - 15.30 Kolmogorov complexity, restricted nondeterminism and
generalized spectra
D. Joseph and M. Sitharam (Madison, USA)
Session 6: Rewriting systems, cryptography (J. Beauquier, Chairman)
16.00 - 16.30 Combinatorial rewriting on traces
V. Diekert (Muenchen, W. Germany)
16.30 - 17.00 Hiding instances in multi-oracle queries
D. Beaver and J. Feigenbaum (Harvard, Murray Hill, USA)
17.00 - 17.30 Semi-commutations and algebraic languages
M. Clerbout and Y. Roos (Lille, France)
Saturday, February 24, 1990
Session 7: Automata and formal languages (C. Choffrut, Chairman)
9.00 - 9.50 Invited lecture: Computational aspects of structural
recursion
K. Indermark (Aachen, W. Germany)
10.15 - 10.45 The ring of k-regular sequences
J.-P. Allouche and J. Shallit (Bordeaux, France & Hanover,
USA)
10.45 - 11.15 Computational power of one-way multihead finite automata
M. Kutylowski (Wroclaw, Poland)
11.15 - 11.45 Caterpillars and context-free languages
M.P. Chytil and B. Monien (Prague, Czechoslovakia & Paderborn,
W. Germany)
11.45 - 12.45 Infinite trees and automata definable relations over w-words
W. Thomas (Aachen, W. Germany)
GENERAL INFORMATION
Location and dates
The conference will be held on February 22-24, 1990 in the Palais des Congres
Place de la Cathedrale right in the historical center of Rouen in front of the
cathedral.
Lunches
The lunches are not included in the registration fees. A list of restaurants
near the Palais des Congres will be provided with the registration kit.
Social event
A reception will be organized on Thursday evening, February 22 by the Conseil
Regional de Haute Normandie.
Access to Rouen and to the Palais des Congres
>From Paris SAINT-LAZARE SNCF train station. Approximately 1 hour travel.
>From Rouen SNCF train station 10 minutes walk to the Palais des Congres.
>From Paris by road: A 13 motorway direct to Rouen.
Payment
Payments will be accepted only in French Francs either by credit card (Visa
International or Master Card) or by banker's draft to the order of AFCET,
Bank Account: 502 650 009-02, BIMP 22 rue Pasquier, F-75008 Paris.
(Please ask your bank to indicate your name and STACS 90 in order to avoid
any error.) Bank charges on payments in other currencies, or for payments
made in any other way, will be at the participants expense and will be
collected at the conference. For French residents only it is also possible
to pay by cheque to the order of AFCET or by CCP. To guarantee your
registration, complete the charge authorization or enclose a copy of your
bank transfer.
Cancellations
Refunds of 50 % will be made if a written request is received by February 8,
1990. No refunds will be made for cancellations received after February 8,
1990. In case of conference cancellation for reasons beyond its control, AFCET
limits its liability to the registration fees already paid.
Proceedings
The proceedings will be published by Springer Verlag (in the series Lecture
Notes in Computer Science) and distributed to registered participants.
Travel discounts
A 20 % reduction for French Railway round trip tickets can be obtained for
the conference dates. Please complete the appropriate portion of the
registration form to receive your discount ticket(s).
Hotel Reservations
Please complete the accomodation reservation form and send it to WAGONS-LITS.
CONFERENCE REGISTRATION FORM - STACS 90
Send this form to: AFCET - STACS 90
156, boulevard Pereire
75017 Paris FRANCE
Telefax: 33-1-42-67-93-12
(Please type or print)
Name: _______________________________ First Name: _________________________
Firm: _______________________________________________________________________
Address: _____________________________________________________________________
Country: ____________________________________________________________________
Phone: ______________________________ Telefax: _____________________________
Number of invoice copies requested: _________________________________________
Invoice to be sent to: ______________________________________________________
ADVANCE REGISTRATION FEE (before February 8, 1990):
Regular fees Student* * Student rate: is applicable
to all students under 28 years
Conference FF 850 FF 350 on the congress day, a copy of
the student card for the
current year is to be enclosed
with the registration form.
For French non AFCET members, add FF 200 for AFCET 1990 membership
LATE REGISTRATION FEE (beginning February 8, 1990):
Regular fess Student*
Conference FF 950 FF 450
PAYMENT: Conference fee: FF ____________________
AFCET membership: FF ____________________
Total: FF ____________________
AFCET membership number: _____________________________________________________
Credit card: ___ Visa Intl ___ Master Card
Credit card #: ______________________________________________________________
Expiration: _________________________________________________________________
Cardholder's name: __________________________________________________________
Signature: __________________________________________________________________
Date: _______________________________________________________________________
TRAVEL*: [ ] Please send me a local railway discount ticket
* available for the conference dates.
ACCOMODATION RESERVATION FORM - STACS 90
To be returned before January 22, 1990 to:
WAGONS-LITS TOURISME - Service Congres - Melle Anne VIBERT - 40 rue Kleber -
92307 LEVALLOIS PERRET CDX - FRANCE
Phone: 33-1-47-59-45-05 Telefax: 33-1-47-59-46-87 Telex: 611 507
(Please type or print)
Name: _______________________________________________________________________
Address: ____________________________________________________________________
Country: ____________________________________________________________________
Phone: _________________________________ Telex: ___________________________
ACCOMODATIONS
Please reserve: [ ] twin bed room(s) shared by 2 persons [ ] single room(s)
in a hotel of ___ stars from _____ to ______ for ___ nights.
Average rates per room and per night, room basis only, taxes and services
included.
Hotel category: Rate (per night): Required deposit per room:
(*) 1 Star FF 120/220 FF 250
2 Star FF 250/300 FF 400
3 Star FF 430/450 FF 600
(*) Number limited
The hotel deposit will be transmitted to the hotel less FF 60 for reservation
fees and will be deducted from your final bill which you must settle before
leaving.
PAYMENT: Hotel deposit FF ___
[ ] Check payable to WAGONS-LITS TOURISME/FRANCE VOYAGES
[ ] Copy of my bank transfer sent to the account 218 085 19 - BNP PARIS
ST LAZARE - Code bankque 30004 - Code Guichet 00819 - Cle RIB 61 -
WAGONS-LITS TOURISME/FRANCE VOYAGES - Code comptable 96/670
The bank charges must be added to the above amount. Any differences will be
requested locally.
[ ] I duly authorize you to debit my ___ Visa Intl ___ Master Card
Credit card #: __________________________________________________________
Expiration: ______________________________________________________________
VERY IMPORTANT: No reservation will be made if the present form is not
accompanied by the corresponding amount.
CANCELLATIONS: Refunds (less FF 60 registration fees) will be made before
January 22, 1990. No refunds will be made for cancellations received after
January 22, 1990.
Signature: ____________________________ Date: _____________________________