[Prev][Next][Index][Thread]
FSTTCS 98, Call for Participation
***********************************************************************
* CALL FOR PARTICIPATION *
***********************************************************************
* *
* FST & TCS '98 *
* *
* FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE *
* 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
http://www.imsc.ernet.in/~fsttcs98/brochure.ps.gz
or by email from "fsttcs98@imsc.ernet.in" .)
GENERAL INFORMATION
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.
INVITED SPEAKERS
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)
SATELLITE EVENTS
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.
VENUE
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.
ORGANIZED BY
The Institute of Mathematical Sciences, Chennai, and SPIC Mathematical
Institute, Chennai.
FOR MORE INFORMATION
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 *).
THURSDAY, DECEMBER 17, 1998
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
Raghavachari
A Hamiltonian Approach to the Assignment of Non-Reusable
Frequencies
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
FRIDAY, DECEMBER 18, 1998
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
Graphs
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
Laster
1800 Business Meeting
1930 Conference Dinner
SATURDAY, DECEMBER 19, 1998
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).
TARGET AUDIENCE
Researchers in the area of Theoretical Computer Science, Formal
Language Theory, Parallel and High Performance Computing, and
Biochemists exploring Molecular Computing.
PARTICIPATION
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.
FOR MORE INFORMATION CONTACT
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)
TARGET AUDIENCE
Graduate students and researchers in the areas of Theoretical Computer
Science and Formal Logic.
PREREQUISITES
Some familiarity with logic at the level of first course and
familiarity with basic complexity classes.
PARTICIPATION
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.
FOR MORE INFORMATION CONTACT
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
REGISTRATION FORM
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".
FOR NON-INDIAN PARTICIPANTS
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.
TRAVEL AND MISCELLANEOUS INFORMATION
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.
ACCOMMODATION
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.
SOCIAL EVENTS
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.
ADDITIONAL INFORMATION
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 *
* *
**********************************************************************
HIGHER END
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.
MIDDLE RANGE
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.
LOWER END
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.
**********************************************************************
PROGRAMME COMMITTEE
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)}
ORGANIZING COMMITTEE
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)
CORRESPONDENCE ADDRESS
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
**********************************************************************