victor@WATSON.IBM.COM (Lane Hemachandra) (04/20/91)
====================================================================
18th International Colloquium on Automata, Languages and Programming
Madrid, Spain
====================================================================
REGISTRATION FEE
Before *May 1, 1991* *After May 1, 1991*
(Hotel availability can only
be guaranteed for bookings
made before May 1, 1991)
Member of EATCS......25,000 pts Member of EATCS......30,000 pts
Non-member...........28,000 pts Non-member...........33,000 pts
Student..............20,000 pts
Accompanying person..15,000 pts Accompanying person..20,000 pts
ACCOMMODATION FEE
(one night must be paid in advance)
One night, breakfast included
Hotel Menphis **** Single room 14,000 pts
(Air conditioned) Double room 16,000 pts
Hotel TRYP *** Single room 11,000 pts
(Air conditioned) Double room 13,000 pts
Hotel LAR Single room 5,700 pts
(Not air conditioned) Double room 7,000 pts
Colegio Mayor
(Not air conditioned)
Only double rooms
Toilet and shower on the corridor Full board 3,000 pts
-------------------------------------------------------------------------
REGISTRATION FORM
Complete one for each participant. Use typewriter or block letters
Together with the registration fee also required is the payment of
1 night's accommodation (in the hotel you have chosen *) which
will reserve your accommodation.
* In the case of those staying in the Colegio Mayor the payment
includes a day full board.
Full name.................................................................
Institute/Company.........................................................
Address...................................................................
Postal code...........Country....................E-mail...................
Arrival day..........time............Departure day.........time...........
I have transferred to:
ATI
Banca Catalana
0015-4059-3614-62
Registration fee .................pts
Accommodation fee
(one night in the Hotel.................)
(one day full board in the Colegio Mayor)
.................pts
Total .................pts
When paying, please, specify your name and the name "ICALP" so as to avoid
any misunderstanding. Please enclose to this registration and
accommodation form the receipt of your payment.
Mail to: Javier Leach Albert
Departamento de Informtica y Automtica
Facultad de Matemticas
Universidad Complutense
28040 MADRID (SPAIN)
PROGRAM
MONDAY, JULY 8, MORNING SESSIONS
10:30 Opening of ICALP 91
Session 1: Logic Programming
(Chairperson: M. Rodrguez-Artalejo)
10:55 Invited Lecture:
On the Fixpoint Semantics of
Logic Programs
G. Levi (Pisa, Italy)
11:45 Logic Programming with
Recurrence Domains
Hong Chen, Jieh Hsiang (Stony
Brook, USA)
12:10 Break
Session 2: Functional Programming
(Chairperson: N. Jones)
12:30 Extensional Embedding of a
Strongly Stable Model of PCF
A. Bucciarelli (Pisa, Italy;
LIENS, France), T. Ehrhard (Paris,
LIENS, France)
12:55 Uniform Ideals and Lazy
Higher-Order Strictness Analysis
C. Ernoult (Marcoussis, France),
A. Mycroft (Cambridge, UK)
13:20 Logical and Computational Aspects
-13:45 of Programming with
Sets/Bags/Lists
V. Breazu-Tannen, R. Subrahmanyam
(Philadelphia, USA)
14:00 LUNCH
AFTERNOON SESSIONS
Session 3: Specification and Verification
(Chairperson: P. Wolper)
15:30 Safety for Branching Semantics
A. Bouajjani, J.C. Fernndez,
S. Graf, C. Rodrguez, J. Sifakis
(Grenoble, France)
15:55 Program Composition and Modular
Verification
L. Fix, N. Francez, O. Grumberg
(Haifa, Israel)
16:20 Model-Checking for Probabilistic
Real-Time Systems
C. Courcoubetis (Crete, Greece),
R. Alur, D. Dill (Palo Alto, USA)
16:45 Computing Behavioural Relations,
Logically
R. Cleaveland (Raleigh, USA),
B. Steffen (Aachen, Germany)
17:10 Break
Session 4: Complexity
(Chairperson: M. Vardi)
17:30 The Power of Reconfiguration
Y. Ben-Asher (Jerusalem, Israel),
D. Peleg (Rehovot, Israel),
R. Ramaswami (Yorktown Heights,
USA), A. Schuster (Jerusalem,
Israel)
17:55 General Resolution of Tseitin
Formulas is Hard
J.-D. Fouks (Mulhouse, France)
18:20 Program Checkers for Probability
Generation
S. Kannan (Rutgers, USA), A. Yao
(Princeton, USA)
18:45 Running Time to Recognize
-19:10 Nonregular Languages by 2-Way
Probabilistic Automata
J. Kaneps, R. Freivalds (Riga,
Latvia)
19:30 University Reception
TUESDAY, JULY 9, MORNING SESSIONS
Session 5: Complexity and Concurrency
(Chairperson: A. Pnueli)
10:30 Invited Lecture:
Statistics on Random Trees
J. Daz, R. Casas, C. Martnez
(Barcelona, Spain)
11:20 The Expressive Power of Implicit
Specifications
K. G. Larsen (Aalborg, Denmark)
11:45 CCS+Time = an Interleaving Model
for Real Time Systems
Wang Yi (Gteborg, Sweden)
12:10 Break
Session 6: Formal Languages
(Chairperson: J. Hromkovic)
12:30 On Confluent Semi-Commutation
Systems-Decidability and
Complexity Results
V. Diekert (Mnchen, Germany),
E. Ochmanski (Warszawa, Poland),
K. Reinhardt (Stuttgart, Germany)
12:55 Lazard's Factorizations of Free
Partially Commutative Monoids
G. Duchamp, D. Krob (Rouen, Paris,
France)
13:20 A Kleene Theorem for Infinite
-13:45 Trace Languages
P. Gastin (Paris, France),
A. Petit (Orsay, France),
W. Zielonka (Talence, France)
14:00 LUNCH
AFTERNOON SESSIONS
Session 7: Rewriting and Logic
(Chairperson: F. Orejas)
15:30 Canonical Sets of Horn Clauses
N. Dershowitz (Urbana-Champaign,
USA)
15:55 A Specialized Completion Procedure
for Monadic String-Rewriting
Systems Presenting Groups
K. Madlener (Kaiserslautern,
Germany), P. Narendran (Albany,
USA), F. Otto (Kassel, Germany)
16:20 A Confluent Reduction for the
lambda-Calculus with Surjective
Pairing and Terminal Object
P.-L. Curien (LIENS, France),
R. Di Cosmo (Pisa, Italy; LIENS,
France)
16:45 Provably Recursive Programs and
Program Extraction
T. Fernando (Palo Alto, USA)
17:10 Break
Session 8: Graph Algorithms
(Chairperson: A. Lingas)
17:30 Efficient Algorithms for Path
Problems with General Cost Criteria
T, Lengauer, D. Theune (Paderborn,
Germany)
17:55 Computing Shortest Paths and
Distances in Planar Graphs
H. N. Djidjev (Sofia, Bulgaria),
G. E. Pantziou, C. D. Zaroliagis
(Patras, Greece)
18:20 Maintaining Biconnected Components
of Dynamic Planar Graphs
Z. Galil (New York, USA; Tel-Aviv,
Israel), G. F. Italiano (New York,
USA; Roma, Italy)
18:45 Efficient Maximal Cubic Graph Cuts
-19:10 M. Loebl (Prague, CSFR)
19:30 EATCS General Assembly
WEDNESDAY, JULY 10, MORNING SESSIONS
Session 9: Complexity
(Chairperson: F. T. Leighton)
10:30 Invited Lecture:
Structural Parallel Algorithmics
U. Vishkin (Maryland, USA;
Tel Aviv, Israel)
11:20 Improving Known Solutions is Hard
D. Ranjan, S. Chari, P. Rohatgi
(Ithaca, USA)
11:45 Collapsing Degrees via Strong
Computation
L. A. Hemachandra (Rochester,
USA), A. Hoene (Berlin, Germany)
12:10 Break
Session 10: Parallel Algorithms
(Chairperson: U. Vishkin)
12:30 Fast Parallel Generation of
Random Permutations
T. Hagerup (Saarbrcken, Germany)
12:55 A Parallel Algorithm for two
Processors Precedence Constraint
Scheduling
H. Jung (Berlin, Germany),
M. Serna (Barcelona, Spain),
P. Spirakis (Patras, Greece)
13:20 An Efficient NC Algorithm for
-13:45 Finding Hamiltonian Cycles in
Dense Directed Graphs
M. Frer, B. Raghavachari
(Pennsylvania, USA)
14:00 LUNCH
EXCURSION
15:30 Departure to Segovia
20:00 Reception at Manzanares Castle
THURSDAY, JULY 11, MORNING SESSIONS
Session 11: Logic in Computer Science (BRA session)
(Chairperson: U. Montanari)
10:30 Invited Lecture:
On Logics, Tilings, and Automata
W. Thomas (Kiel, Germany)
11:20 Satisfiability of Systems of
Ordinal Notations with the Subterm
Property is Decidable
J.-P. Jouannaud (Orsay, France),
M. Okada (Montreal, Canada)
11:45 Complete Axiomatizations of
Some Quotient Term Algebras
H. Common (Orsay, France)
12:10 Break
Session 12: Concurrency (BRA session)
(Chairperson: G. Metakides,
Esprit BRA)
12:30 The Meaning of Negative Premises
in Transition System Specifications
R. Bol, J. F. Groote (Amsterdam,
The Netherlands)
12:55 Deciding History Preserving
Bisimiliarity
W. Vogler (Mnchen, Germany)
13:20 Adding Action Refinement to a
-13:45 Finite Process Algebra
L. Aceto, M. Hennessy (Brighton,UK)
14:00 LUNCH
Session 13: Algorithms
(Chairperson: B. Monien)
15:30 Improved Parallel Computations
with Structured Matrices and
Applications/Fast Parallel
Computation of the Polynomial
Remainder Sequence via Bezout and
Hankel Matrices
V. Pan (Albany, USA), D. Bini
(Pisa, Italy), L. Gemignani
(Firenze, Italy)
15:55 Finding Minimal Forbidden Minors
Using a Finite Congruence
J. Lagergren, S. Arnborg
(Stockholm, Sweden)
16:20 Better Algorithms for the
Pathwidth and Treewidth of Graphs
H. L. Bodlaender, T. Kloks
(Utrecht, The Netherlands)
16:45 Two Problems Dealing with Real
Numbers that are Hard
to Parallelize
F. Cucker, A. Torrecillas
(Barcelona, Spain)
17:10 Break
Session 14: Formal Languages
(Chairperson: J. Karhumki)
17:30 L Morphisms: Bounded Delay and
Regularity of Ambiguity
J. Honkala, A. Salomaa
(Turku, Finland)
17:55 Degree et Decomposability of
Variable-Length Codes
V. Bruyere (Mons, Belgium),
C. de Felice (Baronissi, Italy)
18:20 An Eilenberg Theorem for
-Languages
T. Wilke (Kiel, Germany)
18:45 Balancing Order and Chaos in Image
-19:10 Generation
K. Culik II, S. Dube
(Columbia, USA)
21:00 Conference Dinner
FRIDAY, JULY 12, MORNING SESSION
Session 15: Formal Languages and Complexity
(Chairperson: W. Thomas)
10:30 Invited Lecture:
Average Case Complexity
Y. Gurevich (Ann Arbor, USA)
11:20 NFA Minimization Problems are Hard
Tao Jiang (Ontario, Canada),
B. Ravikumar (Kingston, USA)
11:45 Algorithms for Determining the
Smallest Number of Nonterminals
(States) Sufficient for Generating
(Accepting) a Regular Language
K. Hashiguchi (Toyohashi, Japan)
12:10 Break
Session 16: Computational Geometry
(Chairperson: J.-R. Sack)
12:30 Computing Shortest Transversals
B. Bhattacharya (Burnaby, Canada),
G. Toussaint (Montreal, Canada)
12:55 Ray Shooting in Polygons Using
Geodesic Triangulations
B. Chazelle, H. Edelsbrunner,
M. Grigni (Cambridge, USA),
L. Guibas (Princeton, USA),
J. Hershberger (Palo Alto, USA),
M. Sharir (Tel Aviv, Israel),
J. Snoeyink (Urbana-Champaign, USA)
13:20 The Expected Extremes in a
-13:45 Delaunay Triangulation
M. Bern, D. Eppstein, F. F. Yao
(Palo Alto, USA)
14:00 LUNCH
Session 17: Complexity and
Computational Geometry
(Chairperson: J. Daz)
15:30 Invited Lecture:
Computational Geometry for
the Gourmet: Old Fare and
New Dishes
B. Chazelle (Princeton, USA)
16:20 On the Power of Multiple Reads
in a Chip
P. Duris (Bratislava, CSFR),
Z. Galil (Tel-Aviv, Israel;
New York, USA)
16:45 On Linear Decision Trees Computing
Boolean Functions
H. D. Grger (Szeged, Hungary),
G. Turn (Chicago, USA;
Szeged, Hungary)
17:10 Break
Session 18: Algorithms
(Chairperson: W. Kuich)
17:30 An Almost Linear-Time Algorithm
for the Dense Subset-Sum Problem
Z. Galil (Tel-Aviv, Israel;
New York, USA), O. Margalit
(Tel-Aviv, Israel)
17:55 On-line Algorithms for Weighted
Matching and Stable Marriages
S. Khuller (Maryland, USA),
S. G. Mitchell, V. V. Vazirani
(Ithaca, USA)
18:20 Fast String Matching Preprocessing
of Text and Pattern
M. Naor (San Jos,, USA)
18:45 Ordering Problems Approximated:
Single-Processor Scheduling and
Interval Graph Completion
R. Ravi, A. Agrawal, P. Klein
(Providence, USA)
19:10 End of ICALP
(posted for, and inquiries to:)
Professor Javier Leach Albert
ICALP91%EMDUCM11.BITNET@CUNYVM.CUNY.EDU (ICALP@EMDUCM11.BITNET)
Professor Javier Leach Albert
Departamento de Informtica y Automtica
Facultad de Matemticas
Universidad Complutense
28040 MADRID (SPAIN)