LICS'95 Program & Registration (text & LaTeX)

[Since it is clearly relevant, I am distributing this conference
announcement to types.  -- Philip Wadler, moderator, Types Forum.]

[This announcement is being sent to email lists.  Our apologies
 for multiple copies.
 This information is also available on the world-wide web at
 http://www.research.att.com/lics/, and via anonymous ftp
 from research.att.com, directory /dist/lics.]

                      Tenth Annual IEEE Symposium on
                         Logic in Computer Science

                             June 26-29, 1995
                           San Diego, California

                               Organized by
                    University of California, San Diego

                               Sponsored by
     IEEE Technical Committee on Mathematical Foundations of Computing
                           IEEE COMPUTER SOCIETY

                             with support from
                          AT&T Bell Laboratories
                        IBM Almaden Research Center
                              Rice University
                    University of California, San Diego

                            CONFERENCE PROGRAM

SUNDAY, June 25
CONFERENCE AND HOUSING CHECK-IN                    (11:00am - Midnight)
    Muir Conference Desk, Tenaya Hall

WELCOME RECEPTION                                  (6:00pm-9:00pm)
    Price Center Plaza

MONDAY, June 26

INTRODUCTION                                       (8:30-8:45)
  Moshe Y. Vardi, LICS General Chair

INVITED LECTURE                                    (8:45-9:45)
    Chair: Moshe Y. Vardi (Rice)
  Amir Pnueli (Weizmann Institute):
  Quantified Temporal Logic - Axiomatization and Applications

SESSION 1: PROGRAM LOGICS                          (10:15-11:45)
    Chair: Dexter Kozen (Cornell)

10:15 Completeness of Kozen's Axiomatisation of the 
      Propositional Mu-Calculus,
  Igor Walukiewicz (Aarhus)

10:45 Once and For All,
  Orna Bernholtz (Technion) & Amir Pnueli (Weizmann Institute)

11:15 Complete Proof Systems for First Order Interval Temporal Logic,
  Bruno Dutertre (London)

LUNCH                                              (11:45-1:30)

SESSION 2: FINITE MODELS I                         (1:30-3:30)
    Chair: Val Tannen (U Penn & Paris-Sud)

1:30 The Infinitary Logic of Sparse Random Graphs,
  James F. Lynch (Clarkson) & Jerzy Tyszkiewicz (RWTH Aachen)

2:00 Generalized Quantifiers and 0-1 Laws,
  Anuj Dawar (Wales) & Erich Graedel (RWTH Aachen)

2:30 Relativized Logspace and Generalized Quantifiers over
     Finite Structures,
  Georg Gottlob (TU Wien)

3:00 First-order Queries on Finite Structures over the Reals,
  Jan Paredaens (Antwerp), Jan Van den Bussche (INRIA) & Dirk Van
  Gucht (Indiana)

    Chair: A. P. Sistla (U Illinois, Chicago)      (4:00-6:00)

4:00 Model-Checking of Causality Properties,
  Rajeev Alur (AT&T Bell Labs), Doron Peled (AT&T Bell Labs) &
  Wojciech Penczek (Eindhoven)

4:30 On the Complexity of Modular Model Checking,
  Moshe Y. Vardi (Rice)

5:00 Timing Behavior Analysis for Real-Time Systems,
  Farn Wang (Academia Sinica)

5:30 On the Verification Problem of Nonregular Properties for Nonregular
  Ahmed Bouajjani (Verimag-Spectre), Peter Habermehl (Verimag-Spectre)
  & Rachid Echahed (LGI-IMAG)

DEMO SESSION                                       (8:30pm)

TUESDAY, June 27

INVITED LECTURE                                    (8:30-9:30)
    Chair: Ed Clarke (CMU)
  Michael Gordon (Cambridge):
  The Semantic Challenge of Verilog HDL

SESSION 4: THEOREM PROVING AND AI                  (10:00-12:00)
    Chair: Thomas Henzinger (Cornell)

10:00 Uniform Proofs and Disjunctive Logic Programming,
  Gopalan Nadathur & Donald W. Loveland (Duke)

10:30 Structural Cut Elimination,
  Frank Pfenning (CMU)

11:00 Paramodulation without Duplication,
  Christopher Lynch (INRIA)
11:30 Complexity of Normal Default Logic and Related Modes of Nonmonotonic
  V. Wiktor Marek (Kentucky), Anil Nerode (Cornell) & Jeffrey
  B. Remmel (UC San Diego)

LUNCH                                              (12:00-1:30)

SESSION 5: CONCURRENCY I                           (1:30-3:30)
    Chair: Carolyn Brown (Sussex)

1:30 Control Structures,
  Alex Mifsud (Malta), Robin Milner (Cambridge) & John Power (Edinburgh)

2:00 Configuration Structures,
  R. J. Van Glabbeek (Stanford) & G. D. Plotkin (Edinburgh)

2:30 A Typed Calculus of Synchronous Processes,
  Simon Gay & Rajagopal Nagarajan (Imperial College)

3:00 Modal Mu-Types for Processes,
  Marino Miculan & Fabio Gadducci (Pisa)

SESSION 6: SEMANTICS I                             (4:00-5:30)
    Chair: Martin Abadi (DEC SRC)

4:00 Games and Full Abstraction for the Lazy Lambda-Calculus,
  Samson Abramsky & Guy McCusker (Imperial College)

4:30 Domain Theory in Stochastic Processes
  Abbas Edalat (Imperial College)

5:00 A Fully Abstract Semantics for a Concurrent Functional Language with
     Monadic Types
  Alan Jeffrey (Sussex)

GENERAL MEETING                                    (8:30pm)


INVITED LECTURE                                    (8:30-9:30)
    Chair: Dexter Kozen (Cornell)
  Robert Constable (Cornell):
  Experience with Type Theory as a Foundation for Computer Science

  Chair: Jerzy Tiuryn (Warsaw)                     (10:00-12:00)

10:00 Equality Between Functionals in the Presence of Coproducts,
  Daniel J. Dougherty & Ramesh Subrahmanyam (Wesleyan)

10:30 A Logic of Subtyping,
  Giuseppe Longo (LIENS-CNRS & DMI, Paris), Kathleen Milsted (France
  Telecom CNET) & Sergei Soloviev (Aarhus)

11:00 Normalization and Extensionality,
  Adolfo Piperno (Roma)

11:30 New Notions of Reduction and Non-Semantic Proofs of Beta-Strong
      Normalization in Typed Lambda-Calculi
  A. J. Kfoury & J. B. Wells (Boston U)

LUNCH                                              (12:00-1:30)

SESSION 8: FINITE MODELS II                        (1:30-3:30)
Chair: Phokion Kolaitis (UC Santa Cruz)

1:30 Finitely Monotone Properties,
  Alexei P. Stolboushkin (UC Los Angeles)

2:00 Tree Canonization and Transitive Closure,
  Kousha Etessami & Neil Immerman (U Mass, Amherst)

2:30 Ptime Canonization for Two Variables with Counting,
  Martin Otto (RWTH Aachen)

3:00 When Do Fixed Point Logics Capture Complexity Classes?,
  Anil Seth (Institute of Mathematical Sciences, Madras)

SESSION 9: UNIFICATION AND REWRITING               (4:00-5:30)
    Chair: Leo Bachmair (SUNY Stony Brook)

4:00 Higher-Order Unification via Explicit Substitutions,
  Gilles Dowek (INRIA), Therese Hardin (LITP & INRIA) &
  Claude Kirchner (INRIA & CRIN-Villers-les-Nancy)

4:30 Sequentiality, Second Order Monadic Logic and Tree Automata,
  Hubert Comon (CNRS & LRI-U Paris)

5:00 Orderings, AC-Theories and Symbolic Constraint Solving,
  Hubert Comon (CNRS & LRI-U Paris), Robert Nieuwenhuis (TU Catalonia)
  & Albert Rubio (TU Catalonia)

RECEPTION                                          (5:30pm-6:30pm)
    Stephen Birch Aquarium

DINNER                                             (6:30pm-8:30pm)
    Stephen Birch Aquarium
  After dinner speaker: B. Trakhtenbrot (Tel Aviv)
  Origins and Metamorphoses of the Trinity:
  Logical Nets, Automata, Specifications in Monadic Logic


SESSION 10: MODEL CHECKING II                      (8:30-10:00)
    Chair: E. Allen Emerson (UT Austin)

8:30 Efficient On-the-Fly Model Checking for CTL*
  Girish Bhat (NC State), Rance Cleaveland (NC State) & Orna Grumberg

9:00 Partial Model Checking
  Henrik Reif Andersen (TU Denmark)

9:30 Hardware Verification via Boolean Logic Programming
  Enrico Tronci (L'Aquila)

SESSION 11: CONCURRENCY II                         (10:30-11:30)
    Chair: Ursula Goelz (Hildesheim)

10:30 Compositionality via Cut-Elimination: 
      Hennessy-Milner Logic for an Arbitrary GSOS
  Alex K. Simpson (Edinburgh)

11:00 Compositional Testing Preorders for Probabilistic Processes
  Bengt Jonsson & Wang Yi (Uppsala)

LUNCH                                              (11:30-1:00)

SESSION 12: SEMANTICS II                           (1:00-2:30)
    Chair: C.-H. Luke Ong (Oxford & Natl. U Singapore)

1:00 The Stone Gamut: A Coordinatization of Mathematics
  Vaughan R. Pratt (Stanford)

1:30 Logically Presented Domains
  Erik Palmgren & Viggo Stoltenberg-Hansen (Uppsala)

2:00 Games Semantics for Full Propositional Linear Logic
  Francois Lamarche (Imperial College)

SESSION 13: LINEAR LOGIC                           (3:00-4:30)
    Chair: Dale Miller (U Penn)

3:00 Decision Problems for Second Order Linear Logic
  Patrick Lincoln (SRI), Andre Scedrov (U Penn) & Natarajan Shankar

3:30 The Complexity of Neutrals in Linear Logic
  Max I. Kanovich (Tohoku & Russian Humanities State)

4:00 Decidability of Linear Affine Logic
  Alexei P. Kopylov (Moscow State)


                        CONFERENCE INFORMATION


Please address registration form and inquiries to:

        UCSD, Conference Services
        Cindy Laurence
        Conf. Coordinator LICS'95
        9500 Gilman Drive, Dept. 0513
        La Jolla, CA 92093-0513  USA
        Phone:  (01) (619) 534-4220
        Fax:    (01) (619) 534-2042
        Email:  claurence@ucsd.edu


Mail or fax the completed registration form with payment in
U.S. Currency to UCSD, Conference Services at the above address.  For
early registration, payment must be received by May 26, 1995.  Fees
will be returned in full for any written cancellation received before
June 14.  No refunds will be made after June 14.

A table of registration fees can be found on the registration form.
The member rate applies to: members of ACM, IEEE, and EATCS, members
of the organizing and program committee, and authors of accepted
papers.  The student rate applies to full time students only.
Students must enclose a copy of their 1994-95 student card with the
registration form.

The registration fee includes conference participation, a copy of the
proceedings, coffee breaks and an invitation to the welcome reception.
There is a separate charge for the banquet.

Payment must be in U.S. currency in the form of Visa, Mastercard,
check or money order.  All forms of payment must be drawn on a
U.S. bank.  Checks and money orders should be made payable to: "UC

Once the registration form and remittance have been received, the
Conference Manager will send a receipt and confirmation letter to the
participant's address.


Reasonably priced and comfortable apartment housing is available on
the UCSD campus within walking distance from the conference site.
Each apartment houses three or four people who will share a living
room and a bathroom.  Double rooms with two single beds may be rented
as a double or single room.

Campus housing is sold as a package housing/meal plan only. The
package includes: four nights accommodations, Sunday through Thursday,
and breakfast Monday through Thursday.  Breakfast will be served near
the meeting site.  Dinner for Monday and Tuesday can either be taken
on-campus or at a nearby restaurant.  For restaurant information
inquire at the check-in desk upon arrival.  The banquet will be held
at the Aquarium on Wednesday evening.

Housing is also available to anyone who wishes to arrive early or
depart late.  A fee schedule is printed on the registration form.  The
pre-registration deadline for on-campus housing is May 26.
Registration received after May 26 is subject to availability.
Refunds are available for housing/meal plan if cancellation is made in
writing before June 14.


The conference is being held at the Price Center of the University of
California, San Diego campus.  The campus is located in La Jolla north
of downtown San Diego.  Nearby attractions include the San Diego Zoo
and Seaworld.  UCSD is also well known for the Scripps Institute of
Oceanography which rests on the west end of campus and overlooks the

The weather in La Jolla in June is usually pleasant with temperatures
around 25 degrees C and low humidity.  Evenings can be cooler, down to
17 degrees C, so a light jacket or sweater may be useful.
Occasionally very hot, dry weather (Santa Ana) can occur for a few
days if the prevailing winds shift and come from the inland deserts.
The Pacific Ocean is warm enough for swimming.  We suggest you bring
along swim wear and a beach towel.  You may also wish to bring a hat.


A Welcome Reception will be held on Sunday evening from 6pm-9pm at
UCSD in the Price Center Plaza.  The Conference Banquet will be held
at the Stephen Birch Aquarium on Wednesday, June 28.  Please reserve a
banquet ticket when you complete the registration form.


Lunch and dinner are at the participant's own expense.  Participants
may dine at one of seven restaurants within the Price Center or at one
of the other food service facilities throughout campus.  Participants
staying on campus may have dinner at one of the dining facilities on
campus or at one of the many fine restaurants located in La Jolla.  La
Jolla is approximately 4 miles from campus and may be reached by cab
or bus.

Additional local arrangements information may be obtained on the World
Wide Web at:

The organizers cannot be held liable to conference participants for
injury, damage or loss of their personal property.  It is suggested
that participants make their own insurance arrangements.


Tenaya Hall:    Daily        8am-Midnight   
Price Center:   Sunday       6pm-9pm 
                Mon.-Thurs.  8am-5pm

Housing registration is at Tenaya Hall.  Conference registration is at
the Price Center at the hours listed above and at Tenaya Hall


Please make travel arrangements early.  Summers are a busy travel
period in Southern California.  A special conference fare has been
negotiated with American Airlines for the LICS '95 Conference.  This
applies to domestic reservation only, though international flights may
reference the ID Number to assist us with tracking arrivals and
departures.  Please contact the American Airlines Meeting Services
Desk at (800) 433-1790; to obtain the discount please reference Star
File #S0465HN.

Travelers are entitled to either:

5% off the lowest applicable fare available 
10% off full coach or first class fare 
Allowable travel dates:  June 21-30, 1995

A cab fare from the airport to La Jolla is approximately $30.  A
number of shuttles operate continually outside the baggage claim area.
Peerless Shuttle is recommended as they cost $15/person; see ground
transportation or contact them on a courtesy phone (619-554-1700) at
the airport.  Ask the driver to take you to the Tenaya Hall Conference
Desk on the Muir Campus. (You will probably need to show the driver
the campus map to find Tenaya Hall but he will know where UCSD is!).
Rooms will become available for occupancy starting at 11am on Sunday.


A parking permit is required for participants arriving by private or
rental car.  For those being housed on campus, a parking permit is
included in the package plan.  For those housed off campus, a parking
permit may be purchased at the registration desk (current price is
$15/week).  Parking permits are required seven days a week from 7am to
11pm.  Monitoring of permits tends to be quite diligent!


UCSD has been designated by the University Chancellor as a non-smoking
environment.  Smoking is not permitted within any public buildings on
the campus.  However, smoking is permitted on the grounds and in
campus housing.


The following events will be held in La Jolla, California, June

- PLDI'95, ACM SIGPLAN Conference on Programming Language Design
  and Implementation, June 18-21

- Workshop on Language, Compiler, and Tool Support for Real-Time
  Systems, June 21-22

- PEPM'95, ACM SIGPLAN Symposium on Partial Evaluation and
  Semantics-Based Program Manipulation, June 21-23

- Haskell Workshop, June 25

- FPCA'95, SIGPLAN/SIGARCH/WG2.8 Conference on Functional
  Programming Languages and Computer Architecture, June 25-28

Information may be obtained on the Web at:


    Sam Buss (619) 534-6455
    Jeff Remmel (619) 534-2643
    University of California, San Diego
    Mathematics Department
    9500 Gilman Drive, 0112
    La Jolla, CA 93093-0112  USA
    Email: lics95@math.ucsd.edu


    LICS'95: http://math.ucsd.edu/lics95
    LICS: http://www.research.att.com/lics/

                      LICS'95 REGISTRATION FORM

Please type or print.

Last Name: ______________________________________________________________

First Name: _____________________________________________________________

Affiliation: ____________________________________________________________

Street Address: _________________________________________________________


City: ___________________________________________________________________

State/Zip: ______________________________________________________________

Country: ________________________________________________________________

Phone(s): _______________________________________________________________

Fax: ____________________________________________________________________

E-mail: _________________________________________________________________

CONFERENCE REGISTRATION RATES.  All fees are in U.S. Currency.  Please
circle the applicable fees.

                   Before    On or after
                   May 26      May 26
  Regular          $380.00     $480.00
 *Member           $290.00     $380.00 
  Student          $185.00     $250.00 

                   Before    On or after
                   June 19     June 19

  Banquet          $50.00    Not Available
**Breakfast Only   $23.60    Not Available

* Includes members of ACM, IEEE, and EATCS, members of the organizing
and program committee, and authors of accepted papers.

** Only available to participants who do not reside on campus.

Rate justification: _____________________________________________________

Full-time student at: ___________________________________________________


                  LICS'95 REGISTRATION FORM (cont.)

ON-CAMPUS HOUSING.  June 26-29, 1995 (includes 4 breakfasts).  All
fees are in U.S. Currency.  ** Payment due with registration. **

  Single Room   $179.50 
  Double Room   $147.60

  Additional nights lodging:
  Single Room   $39.00 
  Double Room   $31.00

  Family Apartment:  Please call for rates.

TOTAL DUE (REGISTRATION AND ACCOMMODATION): _____________________________

PAYMENT.  Circle one:

    Check or Money Order 


** All funds must be drawn on a U.S. bank. **

Credit card #: __________________________________________________________

Expiration Date: ________________________________________________________

Signature: ______________________________________________________________

Date: ___________________________________________________________________

PREFERRED ROOMMATE (for those choosing double rooms): 


ARRIVAL DATE: ___________________________________________________________

DEPARTURE DATE: _________________________________________________________


                       CONFERENCE ORGANIZATION

LICS General Chair: Moshe Y. Vardi
1995 Conference Co-chairs: Samuel R. Buss & Jeffrey B. Remmel
1995 Program Chair: Dexter Kozen
Publicity Co-chairs: Amy Felty & Douglas Howe
Program Committee:
  M. Abadi, L. Bachmair, C. Brown, E. Clarke, E.A. Emerson,
  U. Goelz, T. Henzinger, P. Kolaitis, D. Kozen (Chair),
  D. Miller, C.-H.L. Ong, A.P. Sistla, V. Tannen, J. Tiuryn.
Organizing Committee:
  M. Abadi, S. Abramsky, S. Artemov,
  E. Borger, A. Borodin, W. Brauer, A. Bundy, S. Buss, E. Clarke,
  R. Constable, A. Felty, U. Goltz, D. Howe, G. Huet, J.-P. Jouannaud,
  D. Kapur, C. Kirchner, P. Kolaitis, D. Kozen, T. Leighton, D. Leivant,
  A.R. Meyer, D. Miller, J. Mitchell, Y. Moschovakis, M. Okada,
  P. Panangaden, J. Remmel, J. Riecke, S. Ronchi della Rocca,
  A. Scedrov, D. Scott, J. Tiuryn, M.Y. Vardi (Chair).