arvind@utcsri.UUCP (05/20/87)
Date: Mon, 11 May 87 14:00:29 MET
From: "Prof. Dr. Thomas Ottmann" <ottmann%germany.csnet@relay.cs.net>
Subject: ICALP 87
Message-Id: <C066.THEORYNT@ibm.com>
*****************************************************************************
I C A L P 87
14th International Colloquium
on
Automata, Languages and Programming
July 13-17, 1987 Karlsruhe, West Germany
*****************************************************************************
**********************
* SCIENTIFIC PROGRAM *
**********************
MONDAY, JULY 13
9.00 Opening of the conference
Session 1:
----------
Chair: Th. Ottmann (Karlsruhe)
9.15 Invited lecture: Recent Developments in the Theory of Learning
L. Valiant (Harvard University, Cambridge)
10.15 Coffee Break
Session 2: Inductive Inference, Logic and Functional Programming
----------
Chair: H. Kleine Buening (Karlsruhe)
10.45 Probability and Plurality for Aggregations of Learning Machines
L. Pitt (University of Illinois), C.H. Smith (University of Maryland)
11.10 Logic Programming with Ions
M.A. Nait Abdallah (University of Western Ontario)
11.35 Computing Inverse Images
P. Dybjer (University of Goeteborg)
12.00 Lunch
Session 3: Rewrite Systems
----------
Chair: J.P. Jouannaud (Vandoeuvre-les-Nancy)
14.00 A Unification Algorithm for Confluent Theories
S. Hoelldobler (Universitaet der Bundeswehr, Muenchen)
14.25 On the Knuth-Bendix Completion for Concurrent Processes
V. Diekert (Technische Universitaet Muenchen)
14.50 On Word Problems in Equational Theories
J. Hsiang (State University of New York), M. Rusinowitch (CRIN,
Vandoeuvre-les-Nancy)
15.15 Coffee Break
Session 4: Semantics, Concurrency
----------
Chair: W.P. de Roever (Eindhoven)
15.45 Semantics for Nondeterministic Asynchronous Broadcast Networks
R.K. Shyamasundar, K.T. Narayana, T. Pitassi (Pennsylvania State
University)
16.10 Another Look at Abstraction in Process Algebra
J.C.M. Baeten (University of Amsterdam), R.J. van Glabbeek
(Centre of Mathematics and Computer Science, Amsterdam)
16.35 A Timed Failures Model for Extended Communicating Processes
A. Boucher (University of Southern California), R. Gerth
(Eindhoven University)
17.00 Readiness Semantics for Regular Processes with Silent Actions
S. Graf, J. Sifakis (IMAG-LGI, St. Martin-d'Heres)
17.25 Verifying a Protocol Using Relativized Bisimulation
K.G. Larsen (Aalborg University Centre), R. Milner (University
of Edinburgh)
TUESDAY, JULY 14
Session 5:
----------
Chair: P. Deussen (Karlsruhe)
9.00 Invited lecture: On Recent Trends in Formal Language Theory
J. Karhumaeki (University of Turku)
10.00 Coffee Break
Session 6: Formal Languages and Automata I
----------
Chair: B. Monien (Paderborn)
10.20 Non-Uniform Automata Over Groups
D.A. Barrington (University of Massachusetts), D. Therien (McGill
University, Montreal)
10.45 Minimal Automaton of a Rational Cover
D. Beauquier (LITP, Paris)
11.10 A Star-Height Problem in Free Monoids with Partial Commutations
C. Choffrut, C. Duboc (Universite de Rouen)
11.35 Single-Valued Finite Transduction
J.H. Johnson (University of Waterloo)
12.00 Lunch
Session 7: Temporal Logic, Concurrent Systems
----------
Chair: M. Hennessy (Brighton)
14.00 Computation Tree Logic CTL* and Path Quantifiers in the Monadic
Theory of the Binary Tree
T. Hafer, W. Thomas (RWTH Aachen)
14.25 Modelchecking of CTL Formulae under Liveness Assumptions
B. Josko (RWTH Aachen)
14.50 A Model Logic for a Subclass of Event Structures
K. Lodaya (Tata Institute of Fundamental Research, Bombay),
P.S. Thiagarajan (Aarhus University)
15.15 Coffee Break
Session 8: Parallel and Distributed Computing
----------
Chair: A.K. Chandra (Yorktown Heights)
15.45 Parallel 5-Colouring of Planar Graphs
T. Hagerup (Universitaet des Saarlandes, Saarbruecken)
16.10 Parallel Construction of a Suffix Tree
G.M. Landau, B. Schieber (Tel Aviv University), U. Vishkin
(Tel Aviv University and New York University, Courant Institute)
16.35 The Probabilistic and Deterministic Parallel Complexity of
Symmetric Functions
M. Li, Y. Yesha (Ohio State University)
17.00 Term Matching on Parallel Computers
R. Ramesh, R.M. Verma, T. Krishnaprasad, I.V. Ramakrishnan
(State University of New York)
17.25 Guessing Games and Distributed Computations in Synchronous Networks
J.E. van Leeuwen (University of Utrecht), N. Santoro, J. Urrutia
(Carleton University, Ottawa), S. Zaks (Technion, Haifa)
WEDNESDAY, JULY 15
Session 9: Algorithms and Complexity I
----------
Chair: P. Spirakis (Patras)
9.00 Testing the Necklace Condition for Shortest Tours and Optimal Factors
in the Plane
G. Rote, E. Welzl (Technical University of Graz), H. Edelsbrunner
(University of Illinois)
9.25 Nearly Optimal Heuristics for Binary Search Trees with Geometric
Generalizations
C. Levcopoulos, A. Lingas (Linkoeping University), J.-R. Sack
(Carleton University, Ottawa)
9.50 Approximating Integer Lattices by Lattices with Cyclic Factor Groups
A. Paz (Technion, Haifa), C.P. Schnorr (Universitaet Frankfurt)
10.15 Coffee Break
Session 10: Petri Nets, Algebraic Specification
-----------
Chair: W. Menzel (Karlsruhe)
10.45 A Generalization of the Procedure of Karp and Miller to Well
Structured Transition Systems
A. Finkel (Universite Paris-Sud)
11.10 Completeness Results for Reachability, Containment, and Equivalence
with Respect to Conflict-Free Vector Replacement Systems
R. Howell, L. Rosier (University of Texas)
11.35 Partial Algebras Flow from Algebraic Specifications
H.J. Kreowski (Universitaet Bremen)
12.00 Lunch
THURSDAY, JULY 16
Session 11:
-----------
Chair: G. Rozenberg (Leiden)
9.00 Invited lecture: Computer Architecture for Parallel Numerical
Computation
W.J. Paul (Universitaet des Saarlandes, Saarbruecken)
10.00 Coffee Break
Session 12: Formal Languages and Automata II
-----------
Chair: G. Ausiello (Rome)
10.20 The Kleene and the Parikh Theorem in Complete Semirings
W. Kuich (Technische Universitaet Wien)
10.45 An Algorithm for Computing Asynchronous Automata in the Case
of Acyclic Non-Commutation Graphs
Y. Metivier (Universite de Bordeaux I)
11.10 On the Languages Accepted by Finite Reversible Automata
J.E. Pin (LITP Universite Paris VI and CNRS)
11.35 Decision Problems for Regular Trace Languages
I.J. Aalbersberg, H.J. Hoogeboom (Rijks Universiteit Leiden)
12.00 Lunch
Session 13: Complexity
-----------
Chair: J.L. Balcazar (Barcelona)
14.00 The Logarithmic Alternation Hierarchy Collapses
K.J. Lange (Technische Universitaet Muenchen), B. Jenner,
B. Kirsig (Universitaet Hamburg)
14.25 Testing Membership in Commutative Transformation Semigroups
M. Beaudry (McGill University, Montreal)
14.50 On the Computing Power of One-way Cellular Arrays
O.H. Ibarra, T. Jiang (University of Minnesota)
15.15 Coffee Break
Session 14: Algorithms and Complexity II
-----------
Chair: E.M. Schmidt (Aarhus)
15.45 On the Complexity of Graph Critical Uncolorability
J. Cai (Yale University), G.E. Meyer (Cornell University)
16.10 Posets, Boolean Representations and Quick Path Searching
G. Gambosi, M. Talamo (IASI - CNR, Rome), J. Nesetril (Charles
University, Prague)
16.35 The Lexicographically First Maximal Subgraph Problems:
P-Completeness and NC Algorithms
S. Miyano (Universitaet Paderborn and Kyushu University, Fukuoka)
17.00 Uniform Computational Complexity of Taylor Series
N.T. Mueller (FernUniversitaet Hagen)
17.25 Efficient On-line Algorithms for Knapsack Problem
A.M. Spaccamela (University of Rome), C. Vercellis (University of
Milan)
FRIDAY, JULY 17
Session 15:
-----------
Chair: V. Sperschneider (Osnabrueck)
9.00 Invited lecture: The Geometry of Robot Motion Planning
J. Schwartz (Courant Institute, New York University)
10.00 Coffee Break
Session 16: Error Recovery, Algorithms and Complexity III
-----------
Chair: A. Salomaa (Turku)
10.20 Panic Mode without Panic
M.P. Chytil, J. Demner (Charles University, Prague)
10.45 Lower Bounds for Sorting of Sums
M. Dietzfelbinger (University of Illinois)
11.10 The I/O Complexity of Sorting and Related Problems
A. Aggarwal (IBM Watson Research Center), J.S. Vitter (INRIA,
Le Chesnay)
11.35 A Lower Bound for the Complexity of the Union-Split-Find Problem
K. Mehlhorn, S. Naeher (Universitaet des Saarlandes, Saarbruecken),
H. Alt (FU Berlin)
12.00 The Nearest Common Ancestor in a Dynamic Tree
A.K. Tsakalidis (Universitaet des Saarlandes, Saarbruecken)
12.25 Lunch
*****************************************************************************
*****************************
* ADVANCE REGISTRATION FORM *
*****************************
Please type the necessary information at the corresponding places and
send it back by e-mail.
Mail cheque payable in DM (German marks) to ICALP '87 to:
ICALP 87
Prof. Dr. Th. Ottmann
Institut fuer Angewandte Informatik
und Formale Beschreibungsverfahren
University of Karlsruhe (TH)
Postfach 6980
7500 Karlsruhe, F.R.G.
or transfer the registration fee by bank draft to
Baden-Wuerttembergische Bank Karlsruhe
BLZ 660 200 20, account no. 400 20141 03,
Karlsruhe University, Title 28286, BA 515.
Registration fee
----------------
before June 1 after June 1
Member EATCS, GI DM 280,- DM 320,-
Non-member DM 300,- DM 340,-
Student DM 20,- DM 30,-
The fee includes the attendance of the sessions, the proceedings, lunches,
refreshments during the breaks, the Wednesday excursion and the Thursday
conference dinner. Also included is one extra year membership of EATCS for
the members and one year membership of EATCS for the non-members. The
student rate includes only the reception Tuesday evening and coffee breaks.
Additional copies of the conference proceedings can be obtained at DM 45,-
per copy. Please check all appropriate boxes, or enter a number if desired.
___
|___| Special lunch preference: Vegetarian
Total
Extra lunches at DM 14,- per meal
___ ___ ___ ___ ___
Mon |___| Tue |___| Wed |___| Thur |___| Fri |___| _____________
___
|___| Extra banquet at DM 50,- _____________
Program for accompanying persons:
___
|___| Excursion to Stuttgart,
Tuesday, July 14, at DM 30,- _____________
___
|___| Excursion to Baden-Baden,
Thursday, July 16, at DM 30,- _____________
Last name: ______________________________ First name: ___________________
Affiliation: _____________________________________________________________
Address: _________________________________________________________________
_________________________________________________________________
Country: _________________________________________________________________
Telephone or net address: ________________________________________________
___
|___| I am sending a cheque (DM __________ )
___
|___| I have transferred DM __________ to your account.
*********************
* HOTEL RESERVATION *
*********************
We will forward hotel reservations made through e-mail without taking
any liability.
A special arrangement has been made with Ramada Renaissance Hotel; this is
an excellent hotel conveniently situated within 10 minutes walk from the
conference location. All other hotel reservations are handled by
Verkehrsverein Karlsruhe (Tourist Information). A limited number of beds in
dormitory rooms for students is available in the local youth hostel
(Jugendherberge), in walking distance to the university campus, at DM 16,-
per night. Reservations are made on a first-come-first-served basis.
I want to book a room at Ramada Renaissance Hotel:
arrival ________________________________________
arrival time (if after 6 p.m.) _________________
departure ______________________________________
___
Single room with bath: DM 110,-- per night * |___|
___
Double room with bath: DM 150,-- per night * |___|
*Buffet breakfast will be DM 19,50 per day.
Please note that rooms will only be held until 6 p.m. on
arrival date, unless a later arrival has been specified.
***********************************
I want to book a room via Verkehrsverein Karlsruhe:
--------------------------------------------------
| room |number| arrival | departure |
|-------------------------------------------------
| single room | | | |
|-------------------------------------------------
| double room | | | |
|-------------------------------------------------
| with 3 beds | | | |
--------------------------------------------------
___ ___ ___ ___
price range |___| |___| |___| |___| (please mark with a cross)
A B C D
Price ranges, per person:
-------------------------------------------------------------------------
| A : over DM 140,- | rooms with battric Functions
M. Li, Y. Yesha (Ohio State University)
17.00 Term Matching on Parallel Computers
R. Ramesh, R.M. Verma, T. Krishnaprasad, I.V. Ramakrishnan
(State University of New York)
17.25 Guessing Games and Distributed Computations in Synchronous Networks
J.E. van Leeuwen (University of Utrecht), N. Santoro, J. Urrutia
(Carleton University, Ottawa), S. Zaks (Technion, Haifa)
WEDNESDAY, JULY 15
Session 9: Algorithms and Complexity I
----------
Chair: P. Spirakis (Patras)
9.00 Testing the Necklace Condition for Shortest Tours and Optimal Factors
in the Plane
G. Rote, E. Welzl (Technical University of Graz), H. Edelsbrunner
(University of Illinois)
9.25 Nearly Optimal Heuristics for Binary Search Trees with Geometric
Generalizations
C. Levcopoulos, A. Lingas (Linkoeping University), J.-R. Sack
(Carleton University, Ottawa)
9.50 Approximating Integer Lattices by Lattices with Cyclic Factor Groups
A. Paz (Technion, Haifa), C.P. Schnorr (Universitaet Frankfurt)
10.15 Coffee Break
Session 10: Petri Nets, Algebraic Specification
-----------
Chair: W. Menzel (Karlsruhe)
10.45 A Generalization of the Procedure of Karp and Miller to Well
Structured Transition Systems
A. Finkel (Universite Paris-Sud)
11.10 Completeness Results for Reachability, Containment, and Equivalence
with Respect to Conflict-Free Vector Replacement Systems
R. Howell, L. Rosier (University of Texas)
11.35 Partial Algebras Flow from Algebraic Specifications
H.J. Kreowski (Universitaet Bremen)
12.00 Lunch
THURSDAY, JULY 16
Session 11:
-----------
Chair: G. Rozenberg (Leiden)
9.00 Invited lecture: Computer Architecture for Parallel Numerical
Computation
W.J. Paul (Universitaet des Saarlandes, Saarbruecken)
10.00 Coffee Break
Session 12: Formal Languages and Automata II
-----------
Chair: G. Ausiello (Rome)
10.20 The Kleene and the Parikh Theorem in Complete Semirings
W. Kuich (Technische Universitaet Wien)
10.45 An Algorithm for Computing Asynchronous Automata in the Case
of Acyclic Non-Commutation Graphs
Y. Metivier (Universite de Bordeaux I)
11.10 On the Languages Accepted by Finite Reversible Automata
J.E. Pin (LITP Universite Paris VI and CNRS)
11.35 Decision Problems for Regular Trace Languages
I.J. Aalbersberg, H.J. Hoogeboom (Rijks Universiteit Leiden)
12.00 Lunch
Session 13: Complexity
-----------
Chair: J.L. Balcazar (Barcelona)
14.00 The Logarithmic Alternation Hierarchy Collapses
K.J. Lange (Technische Universitaet Muenchen), B. Jenner,
B. Kirsig (Universitaet Hamburg)
14.25 Testing Membership in Commutative Transformation Semigroups
M. Beaudry (McGill University, Montreal)
14.50 On the Computing Power of One-way Cellular Arrays
O.H. Ibarra, T. Jiang (University of Minnesota)
15.15 Coffee Break
Session 14: Algorithms and Complexity II
-----------
Chair: E.M. Schmidt (Aarhus)
15.45 On the Complexity of Graph Critical Uncolorability
J. Cai (Yale University), G.E. Meyer (Cornell University)
16.10 Posets, Boolean Representations and Quick Path Searching
G. Gambosi, M. Talamo (IASI - CNR, Rome), J. Nesetril (Charles
University, Prague)
16.35 The Lexicographically First Maximal Subgraph Problems:
P-Completeness and NC Algorithms
S. Miyano (Universitaet Paderborn and Kyushu University, Fukuoka)
17.00 Uniform Computational Complexity of Taylor Series
N.T. Mueller (FernUniversitaet Hagen)
17.25 E