Thirteenth Annual IEEE Symposium
	      June 21 - 24, 1998, Indianapolis, Indiana


The LICS'98 organizers wish to draw attention to a few
practical matters for which time is of the essence.  For details
please consult the conference web site, http://lics98.cs.indiana.edu.
Specific questions should be addressed to lics98@cs.indiana.edu.

	1. Accommodations at the conference center are limited, 
	and participants are urged to make a reservation promptly,
	notwithstanding the cut-off date of May 20.

	2. The application deadline for accommodations at the 
	student residence ($15 per night) is April 30.
	While students will be given priority, applications from
	all will be considered.

	3. Special LICS'98 air-fares are available from Continental,
	TWA, and US Airways.  The discounts apply to both domestic and
        international flights. 

You can find advance program, registration materials and hotel
information at LICS'98 web sites:

http://lics98.cs.indiana.edu, and 

                           LICS'98 PROGRAM


7:30 - 9:30    RECEPTION


9:00 - 10:00   Invited talk
               Roger Needham (Cambridge University)
               Logic and Over-Simplification
               (Chair: John Mitchell)

10:00 - 10:30  Coffee break

10:30 - 12:30  Session 1: Finite Model Theory I
               (Chair: Erich Graedel)

10:30          Fixed-Point Logics on Planar Graphs
               Martin Grohe (Institut fur Mathematische Logik,

10:55          Existential Second-Order Logic over Strings
               Thomas Eiter (University of Giessen),
               Georg Gottlob (Technische Universitat, Wien),
               Yuri Gurevich (University of Michigan)

11:20 - 11:40  Break

11:40          Finite variable types and generalized quantifiers
               Anuj Dawar (University of Wales), Lauri Hella
               (University of Helsinki), Anil Seth (The Institute of
               Mathematical Sciences, Madras)

12:05          Convergence Results for Relational Bayesian Networks
               Manfred Jaeger (Max-Planck-Institut fur Informatik,

12:30 - 2:00   Lunch

2:00 - 4:35    Session 2: Verification
               (Chair: Doron Peled)

2:00           The Horn Mu-calculus
               Witold Charatonik (Max-Planck-Institut fur Informatik,
               Saarbruecken), David McAllester (AT&T Labs), Damian
               Niwinski (University of Warsaw), Andreas Podelski
               (Max-Planck-Institut fur Informatik, Saarbruecken),
               Igor Walukiewicz (University of Warsaw)

2:25           On Model Checking for Non-Deterministic Infinite State
               E. Allen Emerson, Kedar S. Namjoshi (University of
               Texas at Austin )

2:50           Freedom, Weakness, and Determinism: From Linear-time to
               Orna Kupferman (UC Berkeley), Moshe Y. Vardi (Rice

3:15 - 3:45    Coffee break

3:45           Efficient Representation and Validation of Proofs
               George C. Necula, Peter Lee (CMU)

4:10           Secure Implementation of Channel Abstractions
               Martin Abadi (DEC), Cedric Fournet, 
               Georges Gonthier (INRIA)  

4:35 - 4:55    Break

4:55 - 5:45    Session 3: Logics
               (Chair: Alasdair Urquhart)

4:55           The Logical Role of the Four-Valued Bilattice
               Ofer Arieli, Arnon Avron (Tel-Aviv University)

5:20           Completeness of a Relational Calculus for Program Schemes
               Marcelo F. Frias (Catholic University of Rio de
               Janeiro), Roger D. Maddux (Iowa State University)

8:00           Business Meeting


8:30 - 10:00   Tutorial
               Wolfgang Thomas (University of Kiel)
               Monadic logic and automata: Recent developments
               (Chair: Martin Abadi)

10:00 - 10:30  Coffee break

10:30 - 12:30  Session 4: Concurrency
               (Chair: Luca Aceto)

10:30          Phase Semantics and Verification of Concurrent
               Constraint Programs
               Francois Fages (ENS), Paul Ruet (McGill University), 
               Sylvain Soliman (ENS)

10:55          A Congruence Theorem for Structured Operational
               Semantics of Higher-Order Languages
               Karen L. Bernstein (DePaul University)

11:20 - 11:40  Break

11:40          Bisimulation in name-passing calculi without matching
               Michele Boreale (Universita "La Sapienza"), Davide
               Sangiorgi (INRIA)

12:05          The Fusion Calculus: Expressiveness and Symmetry in
               Mobile Processes
               Joachim Parrow (Royal Institute of Technology, Sweden),
               Bjorn Victor (Uppsala University)

12:30 - 2:00   Lunch

2:00 - 4:10    Session 5: Category Theory
               (Chair: Eugenio Moggi)

2:00           Type Theory via Exact Categories
               L. Birkedal (CMU), A. Carboni (University of Milan),
               G. Rosolini (University of Genoa), D.S. Scott (CMU)

2:25           Higher Dimensional Multigraphs
               Claudio Hermida, Michael Makkai (McGill University)
               John Power (University of Edinburgh)

2:50 - 3:20    Coffee break

3:20           An Axiomatics for Categories of Transition Systems as
               Peter Johnstone (University of Cambridge), John Power
               (University of Edinburgh), Toru Tsujishita and Hiroshi
               Watanabe (Hokkaido University), James Worrell (Oxford

3:45           A Theory of Recursive Domains with Applications to
               Gian Luca Cattani (University of Aarhus), Marcelo
               Fiore (University of Sussex),  Glynn Winskel
               (University of Aarhus)

4:10 - 4:30    Break

4:30 - 6:00    Invited talk
               Dirk van Dalen (University of Utrecht)
               L.E.J. Brouwer's intuitionism: a revolution in two
               (Chair: Bill Rounds)


8:30 - 10:00   Tutorial
               Johan van Benthem (University of Amsterdam)
               Process Operations in Extended Dynamic Logics
               (Chair: Andre Scedrov)

10:00 - 10:30  Coffee break

10:30 - 12:30  Session 6: Theorem Proving and Rewriting
               (Chair: Giuseppe Longo)

10:30          Herbrand's theorem, automated reasoning and semantics
               Andrei Voronkov (Uppsala University)

10:55          The Relation Between Second-Order Unification and
               Simultaneous Rigid E-Unification
               Margus Veanes (Max-Planck-Institut fur Informatik)

11:20 - 11:40  Break

11:40          Decision Problems in Ordered Rewriting
               Hubert Comon (CNRS and LSV), Paliath Narendran (SUNY at
               Albany), Robert Nieuwenhuis (Technical University of
               Catalonia), Michael Rusinowitch (INRIA and CRIN)

12:05          A Stability Theorem in Rewriting Theory
               Paul-Andre Mellies (University of Edinburgh)

12:30 - 2:00   Lunch

2:00 - 3:15    Session 7: Linear Logic
               (Chair: Laurent Regnier)

2:00           Light Affine Logic
               Andrea Asperti (University of Bologna)

2:25           Linear Logic With Boxes
               Ian Mackie (Ecole Polytechnique)

2:50           Coinductive Techniques for Operational Equivalence of
               Interaction Nets
               Maribel Fernandez (ENS), Ian Mackie (Ecole Polytechnique)

3:15 - 3:45    Coffee break

3:45 - 4:35    Session 8: Semantics
               (Chair: Dale Miller)

3:45           A fully abstract game semantics for general references
               Samson Abramsky, Kohei Honda (University of Edinburgh),
               Guy McCusker (St. John's College, Oxford)

4:10           Recursive Types in Games: Axiomatics and Process
               Marcelo Fiore (University of Sussex), Kohei Honda
               (University of Edinburgh)

4:35 - 4:55    Break

4:55 - 6:10    Session 9: Type Theory
               (Chair: Luke Ong)

4:55           Realizability for Constructive Theory of Functions and
               Classes and its Application to Program Synthesis
               Makoto Tatsuta (Kyoto University)

5:20           Completeness of Type Assignment Systems with
               Intersection, Union, and Type Quantifiers
               Hirofumi Yokouchi (Gunma University)

5:45           Full Abstraction for First-Order Objects with Recursive
               Types and Subtyping
               Ramesh Viswanathan (Bell Laboratories)

7:15           BANQUET


9:00  - 10:00  Invited talk
               Moshe Y. Vardi (Rice University)
               Linear time vs. branching time: a complexity-theoretic
               (Chair: Robert Constable)

10:00 - 10:30  Coffee break

10:30 - 11:20  Session 10: Calculi
               (Chair: Edith Hemaspaandra)

10:30          Invertibility in Lambda-Eta
               Enno Folkerts (SAP-AG)

10:55          Calculus in coinductive form
               D. Pavlovic (University of Sussex and Kestrel
               Institute), M.H. Escardo (University of Edinburgh)

11:20 - 11:40  Break

11:40 - 12:30  Session 11:  Constraints and Complexity
               (Chair: Bengt Jonsson)

11:40          The First-Order Theory of Ordering Constraints over
               Feature Trees
               Martin Mueller, Joachim Niehren (University of
               Saarlandes), Ralf Treinen (University of Paris-South)

12:05          On Proofs About Threshold Circuits and Counting Hierarchies
               Jan Johannsen (UCSD), Chris Pollett (Boston University)

12:30 - 2:00   Lunch

2:00 - 3:15    Session 12: Concurrency
               (Chair: Tom Henzinger)

2:00           How to Specify and Verify the Long-Run Average Behavior
               of Probabilistic Systems
               Luca de Alfaro (UC Berkeley)

2:25           Compositional Analysis of Expected Delays in Networks of
               Probabilistic I/O Automata
               Eugene W. Stark, Scott A. Smolka (SUNY at Stony Brook)

2:50           A Logical Characterization of Bisimulation for Labeled
               Markov Processes
               Josee Desharnais (McGill University), Abbas Edalat
               (Imperial College), Prakash Panangaden (McGill University)

3:15 - 3:45    Coffee break

3:45 - 5:45    Session 13: Finite Model Theory II
               (Chair: Moshe Y. Vardi)

3:45           Embedded Finite Models, Stability Theory and the Impact
               of Order
               John T. Baldwin (University of Illinois at Chicago),
               Michael Benedikt (Bell Laboratories)

4:10           On Counting Logics and Local Properties
               Leonid Libkin (Bell Laboratories)

4:35 - 4:55    Break

4:55           On the Boundedness Problem for Two-Variable First-Order
               Phokion G. Kolaitis (UC Santa Cruz), Martin Otto (RWTH

5:20           Fragments of existential second-order logic without 0-1
               Jean-Marie Le Bars (University of Caen)
               [KLEENE PRIZE]


======================= CONFERENCE INFORMATION ======================


Please address forms and inquiries to

	Department of Computer Science
	Indiana University
	Bloomington, IN 47405

	Phone:	+1 (812) 855.4341
	Fax:	+1 (812) 855.4829

	email: 	lics98@cs.indiana.edu
	URL:	http://lics98.cs.indiana.edu	(pending)

Conference desk
Registration and information desks for LICS98 as well as the
affiliated workshops will be located at the Conference Center lobby,
in the areas connecting the hotel to the meeting auditoriums (right
outside the garage elevators).  Assistance will be available also from
the conference information desk on all meeting days, from 6:30am to




			through May 8	from May 9

	member(1) 	325		425
	non-member	425		525
	student(2)	175		225

	Registration package (with copy of the proceedings)
	Daily lunches
	Food service 7:30 - 4:30 (includes coffee breaks)
	Reception and banquet


Fees for 1 or 2 day registration.

			through May 15	from May 16

			1d	2d	1d	2d

	member		150	200	250	300
	non-member	250	300	350	400
	student		90	140	125	175

	Registration package (with copy of the proceedings)
	Lunches for days attended 
	Food service 7:30 - 4:30 (includes coffee breaks)
	LICS Reception

	NB: partial registration fees reflect the same contribution
	to the fixed conference costs as the corresponding full fees.

(1) Member rate applies to members of IEEE Computer Society, ACM, ASL,
or EATCS, as well as to members of the Program and Organizing

(2) Student rate applies to full time students. It does not include
the banquet. 


Pre-LICS workshops: Friday June 19 and Saturday June 20
Post-LICS workshops: Thursday June 25

			through May 15	From May 16

Pre-LICS workshops	$115		$130
Post-LICS workshops	$65		$80

	Registration package
	Lunches for days attended 
	Food service 7:30 - 4:30 (includes coffee breaks)


TO REGISTER, please choose one of the following methods.

 * WEB registration at the URL   http://lics98.cs.indiana.edu

 * EMAIL the form below to  lics98@cs.indiana.edu
		(feel free to add spaces as needed)

 * PRINT the form below and mail or fax it to
	Computer Science Department
	Indiana University
	Bloomington, IN 47405, USA
	Fax: 812-855.4829



FIRST NAME:_____________ 	LAST NAME:___________



EMAIL: __________    PHONE (optional): ____________

SPECIAL REQUESTS/NOTES: ___________________________

	LICS registration fee:				__________

		Please check as appropriate

		* full conference
		* 2 days; dates: ______;_______
		* 1 day; date:   ______

		* non-member
		* member of ______________
		* student, institution: _____________

	Pre-LICS workshops				__________
		You MUST check one workshop,
		for administrative purposes:

		* Probabilistic methods in verification
		* Real Number Computation

	Post-LICS workshops				__________

		You MUST check one workshop,
		for administrative purposes:

		* Game semantics for linear logic
		* Logic & Diagrammatical Information.
		* Model checking & security protocols
	Extra banquet tickets ($35 each)		__________

	Registration total				__________
	If paying with a credit card, processing fee 
		($4 + 2% of registration total)		__________

	TOTAL:						__________

METHOD OF PAYMENT (please check all that applies)

	* Check or money order enclosed 
		(payable to "Indiana University, LICS98")

	* Credit card information enclosed

		* Visa (& Blue Card) OR * MasterCard
			(no other card accepted)

		* Number: ___________________

		* Card's billing address (if different
		from address above):


		* Expiration date:___________

		* Signature (if mailing or faxing):


	* Credit card information called in.
		(Please call 812-855-4341
		during US business hours)




The recommended accommodations are at the Conference Center Hotel,
classified as a 4 diamond hotel by the AAA.  A special LICS98 rate of
$89 for single and $104 for double occupancy is available for the
nights of June 17 through June 26.  These rates are subject to 11%
taxes.  They include parking in the underground garage, but not
breakfast.  Buffet breakfast will be available from 7:30 and the
conference wing; full service breakfast will be available at the
hotel's restaurant.


since the hotel is holding a limited number of rooms, and nearby
hotels are already booked up during the LICS'98 week.  Cancellation is
permitted without penalty till 4pm of the scheduled date of arrival.

To make your reservation call:
	* From the US and Canada: toll-free 800-627-2700
	* From elsewhere: +317-269-9000

Mailing Address: 850 West Michigan Street, Indianapolis, IN 46202
Hotel fax: 317-274-3878
Hotel e-mail: uplace@indycms.iupui.edu


A block of rooms has also been reserved at the Indianapolis Athletic
Club Hotel.  The rate is $85 for single or double, $95 for a
mini-suite (with a small living room), and $125 for a full suite
(large living room).  This hotel occupies a historic building in the
downtown area, about one mile from the conference site.

Mailing Address: 350 North Meridian Street, Indianapolis, IN 46204.
Hotel Phone: 317-634-4331
Hotel Fax: 317-686-4155


Economical accommodations for students have been reserved at the Ball
Residence Building on campus, a short walk from the conference site.
The residence is in active use for summer session, and we were able to
secure only ten beds for male students and ten for female students,
all in double accommodation.  The rate is $14.85 per person per night.

Interested students should address an application to
lics98@cs.indiana.edu, and include any pertinent information about 
their circumstances.  
Applicants are urged to simultaneously make a reservation at one of
the hotels above. 



LICS'98 and its affiliated workshops will take place at the Indiana
University Conference Center in Indianapolis, which combines
state-of-the-art academic meeting facilities with a four star hotel
and various food services.  The Center is located on the Indianapolis
Campus of Indiana University, which includes the university's medical

Indianapolis is a city of about one million inhabitants, located about
250 km south of Chicago.  The Indianapolis downtown area, about one
mile from the conference center, offers a large selection of
restaurants, cultural and entertainment establishments, and modern
up-scale shopping.  It has been a thriving convention location for
over a decade, and is relatively clean and safe.  Other attractions in
and near the city include two art museums of interest, a large
children's museum, a large zoo, a historic park, and the Indy500 race

Additional information and relevant links can be found on the
conference web site, http://lics98.cs.indiana.edu.




Frequent direct flights to Indianapolis are available from most hubs
and gateways in the US.  The conference site is a 20 minute drive from
the airport.  Cab fare from the airport is around $24.

International travelers would normally use a connection in one of the
major US airgates, such as Chicago for United/Lufthansa and
American/British airline alliances as well as others, Detroit for
Northwest/KLM, New York's JFK airport for TWA and many international
carriers, Philadelphia and Pittsburgh for US Airways, New York's
Newark for Continental, and Atlanta or Cincinnati for Delta.  Air
connections from Chicago are particularly frequent, on United (full
jet service) and American (turbojet).  The current lowest fare is $105
for a round trip; however, international airfares can often be
augmented with a connection for a small increment.

Reduced air fares will be offered to LICS participants by Continental
Airlines, TWA, and US Airways.

Continental Airlines offers a discount of 8% on restricted airfare and
13% on unrestricted air fares from the US and Latin America.  The
discounts are 5% and 10%, respectively, for other locations (including
Europe but excluding the Pacific).  In North America call
1-800-322-8662 for reservations, and mention Reference Code NLWM71 (if
booking through a travel agent, also mention the "Z code" ZYE6).

TWA offers discounts of 25% on F25/Y25 fares and 10% on all other
published fares.  These discounts apply to TWA flights worldwide,
except for non-stop flights to and from St. Louis, for which the
discounts are 10% and 5%, respectively. To make reservations in North
America call 800-325.4933, and mention Agreement Number V16412.  You
may also book through a travel agent or a local TWA office, mentioning
the agreement number above.  (NOTE: The TWA reservation system might
not have the LICS98 contract information until April 5.)

US Airways offers a discount of 5% on restricted air fares and 10% on
unrestricted air fares.  These discounts apply systemwide, including
Europe. In North America call 800-334-8644, and mention Gold File
number 156-10-378.

To make reservations for discounted fares outside North America please
contact the respective airline office that serves your area.


Indianapolis is at the crossroad of several major interstate highways,
and is within a day's drive of many US cities.

 From the airport: 
	Airport Expressway (straight E coming from terminal),
	N to I-70 east, exist #79a (West Street),
	N on West Street to Michigan Street,
	W on Michigan Str to University Place Center
	(right after Blake Street on your right)

 From NW (Chicago): 
	I-65 to exit #114 (West Street),
	S to Michigan Street, W on Michigan Str to 
	University Place Center (right after Blake Street on your right)

 From N (South Bend): 
	US 31 all the way through 
	to downtown Indianapolis, pass 10th street, 
	W to Michigan Street, to University Place Center
	(right after Blake Street on your right)

 From SE (Cincinnati): 
	I-74 to I-465, N to I-70, W to I-65,
	W to exit #114 (West Street),
	S to Michigan Street, W to University Place Center
	(right after Blake Street on your right)

 Driving Instructions to Indianapolis Athletic Club:
   From the airport: 
	Airport Expressway (straight E coming from terminal),
	N to I-70 east, exit #79b (Pennsylvania Street)
	N to Meridian Street, N on Meridian to the Club
	(right after New York Street on your left)

   From NW (Chicago): 
	I-65 to exit #113 (Meridian Street),
	S on Meridian to the Club
	(right after Vermont Street on your right)

   From N (South Bend): 
	US 31 all the way through 
	to downtown Indianapolis (Meridian Street), 
	to the Club (right after Vermont Street on your right)


Parking for the conference center is at the University Place Garage,
and is free for all hotel guests and conference registrants.

Parking at the Athletic Club: Use the Denison Garage on 327 North
Illinois, and take the elevated walkway on level 3B straight into the
Club.  The rate is $6 per day.  The garage closes at midnight and on
weekend, and which times street parking is unproblematic.

STREET PLAN (detailed plans will be included with registration package)

		     Blackford        Senate         Illinois	
			||	||	||	||     ^||	||
			||	||	||     |||     |||	||
  *UP*	||   ||   ||	||	||	||     v||	||	||
	||   ||   ||	||	|| <--  ||	|| <--	|| 	||
===================================================================== Michigan
<--			||	||    	|| 	||	||	||
			||	||	||	||	||	||
			||	||	||	||	||	||
                        ||=========================================== Vermont
			||	||    	|| 	||	||	||
			||	||	||	||	|| *AC* ||
			||	|| -->	||	|| -->	|| 	||
	============================================================= New York
			||	||	||	||	||	||
			||	||	||	||	||	||
			       West           Capitol         Meridian


UP  = University Place Conference Center
AC  = Indianapolis Athletic Club