FSTTCS 98, Call for Participation

*                       CALL FOR PARTICIPATION                        *
*                                                                     *
*                         FST & TCS '98                               *
*                                                                     *
*               December 17--19, 1998, Chennai, India                 *
*                                                                     *
*       Conference Home-page at http://www.imsc.ernet.in/~fsttcs98    *

(A postscript version of this announcement is available at
 or by email from "fsttcs98@imsc.ernet.in" .)


The eighteenth Conference on Foundations of Software Technology and
Theoretical Computer Science (FST&TCS-18) will be held at
Chennai. This annual conference provides a platform for presentation
of original research results in fundamental aspects of computer
science. It also provides an excellent forum for meeting and
exchanging ideas with people who are at the frontline of software
technology and theoretical computer science. The proceedings of this
conference are published by Springer Verlag in the LNCS series. 


Rajeev Alur (University of Pennsylvania and Bell Labs)
Ken McMillan (Cadence Berkeley Laboratories)
Neil Immerman (University of Massachussets)
John Reif (Duke University)
Erik Meineche Schmidt (Aarhus University)
Umesh Vazirani (University of California at Berkeley)


The conference will be preceded by a two-day workshop on Molecular
Computing (December 14-15, 1998), and a two-day school on Finite Model
Theory (December 15-16, 1998).  More details of these events are given
below, after the Conference Programme.


The Conference will take place in the auditorium of SAMEER, in the
C.I.T.  campus. Some of the parallel sessions will take place at the
Institute of Mathematical Sciences, close by. 


The Institute of Mathematical Sciences, Chennai, and SPIC Mathematical
Institute, Chennai.


Email  : fsttcs98@imsc.ernet.in
URL    : http://www.imsc.ernet.in/~fsttcs98
Mirror : http://www.smi.ernet.in/~iarcs/fsttcs98
Post   : 18th FST&TCS 1998, 
         The Institute of Mathematical Sciences,
         CIT Campus,
         Chennai 600 113, India
Phone  : +91 44 2351856
Fax    : +91 44 2350586 

*                                                                    *
*                        CONFERENCE PROGRAMME                        *
*                                                                    *

(Parallel sessions are marked with a *).


0815-0900  Registration

0900-1000  Invited Talk 1

     Descriptive Complexity and Model Checking
     Neil Immerman (Univ. Massachussets, Amherst, USA)

1000-1020  Tea

1020-1120  Session 1(a)*

     Approximation Algorithms with Bounded Performance Guarantees for
     the Clustered Traveling Salesman Problem
     Nili Guttmann-Beck, Refael Hassin, Samir Khuller, Balaji
     A Hamiltonian Approach to the Assignment of Non-Reusable
     Dimitris A. Fotakis, Paul G. Spirakis
1020-1120  Session 1(b)*

     Deadlock Sentive Types for Lambda Calculus with Resources
     Carolina Lavatelli
     On encoding p$\pi$ in m$\pi$
     Paola Quaglia, David Walker
1130-1230  Session 2(a)*

     Improved Methods for Approximating Node Weighted Steiner Trees
     and Connected Dominating Sets
     Sudipto Guha, Samir Khuller
     Red-Black Prefetching: An Approximation Algorithm for Parallel
     Disk Scheduling
     Mahesh Kallahalla, Peter J. Varman

1130-1230  Session 2(b)*

     A synchronous semantics of higher-order processes for modeling
     reconfigurable reactive systems
     Jean-Pierre Talpin, David Nowak
     Testing Theories for Asynchronous Languages
     Ilaria Castellani, Matthew Hennessy
1230-1400  Lunch

1400-1500  Invited Talk 2

     Alternative Computational Models: A Comparison of Biomolecular
     and Quantum Computation
     John H. Reif (Duke Univ., USA)
1500-1520  Tea

1520-1620  Session 3

     Optimal Regular Tree Pattern Matching Using Pushdown Automata
     Maya Madhavan, Priti Shankar
     Locating Matches of Tree Patterns in Forests
     Andreas Neumann, Helmut Seidl

1630-1730  Session 4

     Benefits of Tree Transducers for Optimizing Functional Programs
     Armin Kuehnemann
     Implementable Failure Detectors in Asynchronous Systems
     Vijay K. Garg, J. Roger Mitchell


0900-1000  Invited Talk 3

     BRICS and Quantum Information Processing
     Erik Meineche Schmidt (BRICS, Aarhus University, Denmark)

1000-1020  Tea

1020-1120  Session 5(a)*

     Martingales and Locality in Distributed Computing
     Devdatt P. Dubhashi

     Space Efficient Suffix Trees
     Ian Munro, Venkatesh Raman, S. Srinivasa Rao
1020-1120  Session 5(b)*

     Formal Verification of an O.S. Submodule
     N.S.Pendharkar, K.Gopinath
     Infinite Probabilistic and Nonprobabilistic Testing
     K. Narayan Kumar, Rance Cleaveland, Scott A. Smolka
1130-1230  Session 6(a)*

     On Generating Strong Elimination Orderings of Strongly Chordal
     N. Kalyana Rama Prasad, P. Sreenivasa Kumar

     A Parallel Approximation Algorithm for Minimum Weight Triangulation
     Joachim Gudmundsson, Christos Levcopoulos
1130-1230  Session 6(b)*

     The Power of Reachability Testing for Timed Automata
     Luca Aceto, Patricia Bouyer, Augusto Burgueno, Kim G. Larsen

     Recursive Mean-Value Calculus
     P.K. Pandya, Y.S. Ramakrishna
1230-1400  Lunch

1400-1500  Invited Talk 4

     Efficient Formal Verification of Hierarchical Descriptions
     Rajeev Alur (Univ. Pennsylvania and Bell Labs, USA)

1500-1520  Tea

1520-1620  Invited Talk 5

     Proof rules for model checking systems with data
     K. L. McMillan (Cadence Berkeley Labs, USA)

1630-1730  Session 7

     Partial Order Reductions for Bisimulation Checking
     Michaela Huhn, Peter Niebert, Heike Wehrheim
     First-Order-CTL Model Checking
     Juergen Bohn, Werner Damm, Orna Grumberg, Hardi Hungar, Karen

1800       Business Meeting

1930       Conference Dinner


0900-1000  Invited Talk 6

     Quantum Computation and Information
     Umesh Vazirani (Univ. California, Berkeley, USA)
1000-1020  Tea

1020-1120  Session 8(a)*

     On the complexity of counting the number of vertices moved by
     graph automorphisms
     Antoni Lozano, Vijay Raghavan

     Remarks on Graph Complexity
     Satyanarayana V. Lokam

1020-1120  Session 8(b)*

     On the Confluence of Trace Rewriting Systems
     Markus Lohrey
     A String-rewriting Characterization of Muller and Schupp's
     Context-free Graphs
     Hugues Calbrix, Teodor Knapik

1130-1230  Session 9

     Different Types of Monotonicity for Restarting Automata
     P. Jancar, F. Mraz, M. Platek, J. Vogel

     A Kleene iteration for parallelism
     Kamal Lodaya, Pascal Weil

1300  Closing session

1330  Lunch

*                                                                    *
*                          SATELLITE EVENTS                          *
*                                                                    *

                   WORKSHOP ON MOLECULAR COMPUTING                   
                        December 14--15, 1998                        
                        I.I.T. Madras, Chennai                       

Molecular Computing or DNA Computing is one of the fastest growing
research areas in Computing Science.  The question whether DNA could
be used as the basis of a computing device has given rise to a new
topic of research.  Scientists all over the world are exploring the
possibility of building `biochips'.  Adleman's experiment to find a
Hamiltonian path in a graph using chemical reaction on DNA has started
this new exciting area of research.

It is clear that biochemists and Computer Scientists need to work
together to achieve practical results in this area.  It is of interest
to the Computer Scientist to find out what is possible and what is not
possible if and when such a `biochip' could be built.  It would also
be necessary to find out how easy or difficult it would be to solve
problems in such a system.  Since manipulation with DNA is
intrinsically parallel in nature, the algorithms developed should
exploit the massive parallelism available.  The complexity measures
will naturally be different from the ones for existing machines.  Also
there is a spurt of activity in Formal Language Theory because of this
development.  Starting from the work of Tom Head on Splicing systems
to model the recombinant behaviour of DNA sequences, Paun and others
have defined several variations of such systems as well as automata
like Watson-Crick automata.  Probing the generative capacity and
properties of such systems seems to be an interesting topic for
researchers in Formal Language Theory.

In this Workshop the concentration will be on the theoretical aspects
of DNA computing, like design of algorithms for problems using DNA and
studying their complexity.  We also take a closer look at various new
grammar and automata models that emerged due to the developments in
molecular computing.

Several prominent researchers will give talks at the workshop.  Among
them are Natasha Jonoska (USA), Kamala Krithivasan (India),
Georghe Paun (Romania), John Reif (USA), Yasubami Sakakibara (Japan),
Rani Siromoney (India), and K G Subramanian (India).


Researchers in the area of Theoretical Computer Science, Formal
Language Theory, Parallel and High Performance Computing, and
Biochemists exploring Molecular Computing.


For logistic reasons, participation in the Workshop will be limited to
about sixty participants. Interested persons should write to the
address below before November 15, 1998.
The workshop is organised by Kamala Krithivasan.


Prof. Kamala Krithivasan
Department of Computer Science and Engineering,
Indian Institute of Technology, Madras,
Chennai 600036, India.
E-mail: kamala@iitm.ernet.in

                    SCHOOL ON FINITE MODEL THEORY                    
                        December 15--16, 1998                        
                            IMSc, Chennai                            

Finite model theory is concerned with the study of various logical
languages over classes of finite structures. This area has some
affinity with classical model theory but has developed a distinct
identity, both in terms of the questions considered and the techniques
used.  The questions it is concerned with are motivated by connections
with computation, and it has developed a variety of logics and new
techniques for studying their expressive power over finite structures.

Since its inception, finite model theory has had strong connections
with complexity theory and database theory. Recently, it has also
forged some connections with model checking, verification and dynamic
complexity, with its techniques contributing to these areas.

In this school, lectures will be given on core as well as on
application areas of finite model theory by the following speakers
(listed in alphabetical order).
  Anuj Dawar (Univ. of Wales Swansea)
  Martin Grohe (Univ. of Freiburg)
  Neil Immerman  (Univ. of Massachusetts at Amherst)
  Anil Seth (Inst. of Mathematical Sciences, Madras)
  Wolfgang Thomas (Univ. of Aachen)
  Moshe  Vardi (Rice University, Texas)
  Victor Vianu (University of California, San Diego)


Graduate students and researchers in the areas of Theoretical Computer
Science and Formal Logic.


Some familiarity with logic at the level of first course and
familiarity with basic complexity classes.


For logistic reasons, participation in the Workshop will be limited to
about sixty participants. Interested persons should write to the
address below before November 15, 1998.
The workshop is jointly organised by Anil Seth and Anuj Dawar.


Anil Seth
Theoretical Computer Science,
The Institute of Mathematical Sciences,
C. I. T. Campus, Taramani,
Chennai 600113, India.
E-mail: seth@imsc.ernet.in

*                                                                    *
*                      REGISTRATION INFORMATION                      *
*                                                                    *

The registration fees for the conference are as follows:

         |     Dates        |  General | Student |
         | Until Nov. 15    |  US$ 175 | US$ 125 |
         | After Nov. 15    |  US$ 200 | US$ 150 |

The registration fee includes a copy of the conference proceedings,
lunch and refreshments on the days of the conference. 

To pay the registration fee in advance, mail a banker's cheque of the
appropriate value in US Dollars, drawn in favour of "FST&TCS-18"
and payable at the State Bank of India, Adyar, Chennai, India
to the following address:

18th FST&TCS 1998, 
The Institute of Mathematical Sciences,
CIT Campus, 
Chennai 600 113, India


The registration form is part of the Postscript version of this
announcement at "http://www.imsc.ernet.in/~fsttcs98/brochure.ps.gz".
Alternatively, the registration form may be obtained by sending email
to "fsttcs98@imsc.ernet.in".


The Conference needs to forward to the External Affairs Ministry of
the Government of India some particulars of participants with
nationality other than Indian. Non-Indian nationals attending FST\&TCS
and /or the satellite events should obtain a copy of the form listing
the information required by the Government of India.  

The form is part of the Postscript version of this announcement at
"http://www.imsc.ernet.in/~fsttcs98/brochure.ps.gz".  Alternatively,
the form may be obtained by sending email to "fsttcs98@imsc.ernet.in".

The form must be signed by the participant, so a hard-copy of the
filled-out form must be mailed/faxed to the conference organizers.


Chennai, formerly known as Madras, is served by several international
airlines, including Air India, British Airways, Lufthansa, Singapore
Airlines, Malaysian Airlines, Gulf Air. In addition, it has excellent
domestic air and train connections to Delhi and Mumbai (formerly
Bombay), which are served by virtually all international airlines.

Most international flights to/from India in December are booked months
in advance, since this is the prime tourist season. So you are advised
to start making your trip preparations at once. You are also advised
to apply early for a visa, since there can be a large delay in this
process. It is often simpler to apply for a *general tourist visa*
than to get a visa to attend the conference.

The climate in Chennai in December is usually quite pleasant, with day
temperatures ranging between 25 deg C and 30 deg C, and minimum
temperatures of 18 deg C to 20 deg C. Occasional rain showers are
common in December.


The FST&TCS Conference has not made any specific hotel bookings. A
list of conveniently located hotels, with tariff rates and telephone
and FAX numbers, is attached. You can download maps of Chennai and the
area around C.I.T. campus off the conference page. Contact the hotel
of your choice directly and finalise your accommodation
arrangements. Again, since this is the prime tourist season, you are
advised to finalise the hotel booking as early as possible.


A cultural programme will be organized at the Conference venue itself,
on the evening of 17th December. In addition, since the second half of
December is the classical music and dance season in Chennai, there
will be a surfeit of excellent performances all over town. Information
about these events will be available at the Conference registration
desk during the Conference.

There are several interesting sites near Chennai worth a visit.  If
there is sufficient interest, a full-day excursion to the temple town
of Kancheepuram and the temples and beaches of Mamallapuram can be
organized on 20th Deceember. Tentative rates for the excursion will be
made available shortly on the conference homepage.


For more information, see the conference homepage, or send email to
"fsttcs98@imsc.ernet.in".  In particular, detailed instructions and
maps describing how to reach the conference venue will be posted on
the homepage.

*                                                                    *
*                         HOTELS IN CHENNAI                          *
*                                                                    *


Hotel Park Sheraton ***** 
 Rates:  Corporate       :  US$150 + 30% Tax
         Sheraton Towers :  US$240 + 30% Tax
         Suite           :  US$275 + 30% Tax 
         For double occupancy, US$10 extra.
 Contact Information: Tel: +91-44-4994101
                      Fax: +91-44-4997101 

 Comments: Quite close to venue. (6km) 
Hotel Chola Sheraton *****

 Rates:  Deluxe              : US$140 + 30% Tax              
         Exec. Club Room     : US$180 + 30% Tax     
         Club Exclusive Room : US$220 + 30% Tax 
         For double occupancy, US$10 extra. 

 Contact Information: Tel: +91-44-8280101 
                      Fax: +91-44-8278779  

 Comments: Quite close to venue. (8km)

Hotel Taj Coramandel *****

 Rates:  Single room        : US$195 + 30% Tax                  
         Double room        : US$215 + 30% Tax                  
         Deluxe single room : US$215 + 30% Tax           
         Deluxe double room : US$235 + 30% Tax           
         Club: Single - US$275, Double - US$290 ; + 30% Tax 

 Contact Information: Tel: +91-44-8272827 
                      Fax: +91-44-8257104  

 Comments: A bit far from venue (10km). In centre of the city.


Hotel Residency ***

 Rates:  Single room : Rs.1195 + 30% Tax 
         Double room : Rs.1600 + 30% Tax  

 Contact Information: Tel: +91-44-8253434 
                      Fax: +91-44-8250085  

 Comments: Quite close to venue (7km).  Close to centre of the city.
           Increase in rates from Oct 1st.

Hotel Shelter ***

 Rates:  Single room        : Rs.1090 + 20% Tax    
         Double room        : Rs.1330 + 20% Tax    
         Deluxe Double room : Rs.1650 + 20% Tax

 Contact Information: Tel: +91-44-4951919 
                      Fax: +91-44-4935646 

 Comments: Not very far from venue (7km).  Close to Kapaleeshwar Temple.

The Sindoori Hotel ***

 Rates:  Single room               : Rs.1300 + 22% Tax             
         Double room               : Rs.1900 + 22% Tax             
         Deluxe Single/Double room : Rs.2500 + 22% Tax 
         Suite: Rs.3500 + 22% Tax                      

 Contact Information: Tel: +91-44-8271164 
                      Fax: +91-44-8275838  

Hotel Palmgrove ***

 Rates:  Non airconditioned (A/c) Single room : Rs.780 (incl. taxes)  
         Non A/c Double room                  : Rs.840 (incl. taxes)  
         A/c Single room                      : Rs.1080 (incl. taxes)     
         A/c Single room                      : Rs.1140 (incl. taxes)  

 Contact Information: Tel: +91-44-8271881 
                      Fax: +91-44-8231577  

 Comments: A bit far from venue (10km). In centre of city.
           Serves only vegetarian food. 

Hotel Nilgiri's Nest

 Rates:  Single room        : Rs.850 + 20% Tax                         
         Double room        : Rs.1200 + 20% Tax                        
         Semi-deluxe-Single : Rs.1050 + 20% Tax 
         Semi-deluxe-Double : Rs.1550 + 20% Tax 
         Deluxe-Single      : Rs.1400 + 20% Tax 
         Deluxe-Double      : Rs.2050 + 20% Tax         

 Contact Information: Tel: +91-44-8275111, +91-44-8275222, +91-44-8263770, 
                           +91-44-8230716, +91-44-8263774    
                      Fax: +91-44-8260214  

Hotel Kanchi

 Rates:  Single room : Rs.775 + 30% Tax 
         Double room : Rs.800 + 30% Tax  

 Contact Information: Tel: +91-44-8271100 
                      Fax: +91-44-8272928  
 Comments: Quite far from venue (14km). Serves only vegetarian food. 


Hotel Woodlands

 Rates:  Single room non-a/c : Rs.250 + 25% Tax 
         Double room a/c     : Rs.600 + 25% Tax     
         Deluxe Double room  : Rs.800 + 25% Tax  
         Cottage double      : Rs.1100 + 25% Tax  

 Contact Information: Tel: +91-44-8273111 
                      Fax: +91-44-8260460  

 Comments: Clean and comfortable. Serves only vegetarian food. 

Hotel Ganpath

 Rates:  Single room Non-A/c : Rs.550 + 20% Tax  
         Single room A/c     : Rs.700 + 20% Tax      
         Double occupancy    : Rs.50 extra              

 Contact Information: Tel: +91-44-8271889 
                      Fax: +91-44-8260096 

If you require any additional information, please send us mail and we
will try to help. The above list of hotels is by no means
comprehensive; however it does include the hotels most conveniently
located with respect to the conference venue and the city centre.

Currently, the conversion rate for Indian rupees is approximately
Rs.43 per US$.

For telephone calls, the country code for India is 91 and the city
code for Chennai is 44 (these are included with the numbers above).
For calls within India from outside Chennai, replace the prefix +91-44
by 044.  Within Chennai, no prefix is required.



Manindra Agrawal (IIT, Kanpur)
V Arvind (IMSc, Chennai) (Co-Chair)
Jin-Yi Cai (SUNY, Buffalo)
Ramesh Hariharan (IISc, Bangalore)
Kamala Krithivasan (IIT, Chennai)
Meena Mahajan (IMSc, Chennai)
Madhavan Mukund (SMI, Chennai)
Mogens Nielsen (BRICS, Aarhus)
Tobias Nipkow (TU, Muenchen)
C Pandurangan (IIT, Chennai)
Rohit Parikh (CUNY, New York)
Sanjiva Prasad (IIT, Delhi)
Jaikumar Radhakrishnan (TIFR, Mumbai)
R Ramanujam (IMSc, Chennai) (Co-chair)
S Ramesh (IIT, Mumbai)
Abhiram Ranade (IIT, Mumbai)
Sandeep Sen (IIT, Delhi)
Natarajan Shankar (SRI, California)
G Sivakumar (IIT, Mumbai)
Aravind Srinivasan (NUS, Singapore)
pK V Subrahmanyam (SMI, Chennai)
K G Subramanian (MCC, Chennai)
Moshe Vardi (Rice Univ, Texas)
Pascal Weil (CNRS, Paris)}


Kamal Lodaya (IMSc, Chennai)
Meena Mahajan (IMSc, Chennai) (Co-chair)
Madhavan Mukund (SMI, Chennai) (Co-chair)
R. Rama (IIT, Chennai)
Venkatesh Raman (IMSc, Chennai)
Anil Seth (IMSc, Chennai)


Email  : fsttcs98@imsc.ernet.in
URL    : http://www.imsc.ernet.in/~fsttcs98
Mirror : http://www.smi.ernet.in/~iarcs/fsttcs98
Post   : 18th FST&TCS 1998, 
         The Institute of Mathematical Sciences,
         CIT Campus,
         Chennai 600 113, India
Phone  : +91 44 2351856
Fax    : +91 44 2350586