bm@UNI-PADERBORN.DE (Burkhard Monien) (02/21/91)
18th International Colloquium on Automata, Languages and Programming
====================================================================
Program
=======
Monday, July 8, Morning Sessions
--------------------------------
10:30 Opening of ICALP 91
Session 1: Logic Programming (Chairperson: M. Rodriguez-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, U.K)
13:20 Logical and Computational Aspects of Programming with /Bags/Lists
-13:45 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. Fernandez, S. Graf, C. Rodriguez, 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 I (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 Nonregular Languages by 2-Way
Probabilistic Automata
-19:10 J. Kaneps, R. Freivalds (Riga, Latvia)
19:30 University Reception
Tuesday, July 9, Morning Sessions
---------------------------------
Session 5: Concurrency and Complexity (Chairperson: A. Pnueli)
10:30 Invited Lecture:
Statistics on Random Trees
J. Diaz, R. Casas, C. Martinez (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 (Goeteborg, Sweden)
12:10 Break
Session 6: Formal Languages I (Chairperson: J. Hromkovi c )
12:30 On Confluent Semi-Commutation Systems- Decidability and Complexity
Results
V. Diekert (Muenchen, 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 Trace Languages
-13:45 P. Gastin (Paris, France), A. Petit (Orsay, France), W. Zielonka
(Talence, France)
14:00 LUNCH
Afternoon Sessions
Session 7: Rewriting, 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:45 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 10th, Morning Sessions
--------------------------------------
Session 9: Complexity II (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 (Saarbruecken, 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 Finding Hamiltonian Cycles in Dense
Directed Graphs
13:45 M. Fuerer, B. Raghavachari (Pennsylvania, USA)
14:00 LUNCH
Excursion
15:30 Departure to Segovia
19:30 Reception at Manzanares Castle
Thursday, July 11, Morning Session
----------------------------------
Session 11: Logic in Computer Science (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. Comon (Orsay, France)
12:10 Break
Session 12: Concurrency (Chairperson: G. Metakides, Esprit B.R.A.)
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 (Muenchen, Germany)
13:2O Adding Action Refinement to a Finite Process Algebra
-13:45 L. Aceto, M. Hennessy (Brighton, U.K.)
14:00 LUNCH
Session 13: Algorithms I (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 II (Chairperson: J. Karhumaeki )
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 infinite-Languages
T. Wilke (Kiel, Germany)
18:45 Balancing Order and Chaos in Image Generation
-19:10 K. Culik II, S. Dube (Columbia, USA)
19:30 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 Delaunay Triangulation
-13:45 M. Bern, D. Eppstein, F.F. Yao (Palo Alto, USA)
14:00 LUNCH
Session 17: Complexity and Computational Geometry (Chairperson: J. Diaz)
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. Groeger (Szeged, Hungary), G. Turan (Chicago, USA; Szedged,
Hungary)
17:10 Break
Session 18: Algorithms II (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 Jose, 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