The 25th Conference on Foundations of Software Technology and Theoretical Computer Science

December 15-18, 2005
International Institute of Information Technology
Hyderabad, INDIA

IARCS, the Indian Association for Research in Computing Science announces the 25th Annual FSTTCS Conference in Hyderabad. The FSTTCS conference is a forum for presenting original results in foundational aspects of Computer Science and Software Technology.

Invited Speakers

The invited talks in this year's conference will be given by the following eminent researchers: Manindra Agrawal, Tom Henzinger, Russell Impagliazzo, Raimund Seidel, Natarajan Shankar, Joel Spencer and Igor Walukiewicz.


In addition to invited talks and contributed papers, the FSTTCS 2005 programme will have two pre-conference workshops:

Software verification, organized by P. Madhusudan and Sriram Rajamani,
on December 13 and 14, 2005.

Algorithms in Networking, organized by Amit Kumar and Aravind Srinivasan
on December 14, 2005.

List of accepted papers

The Programme Committee is pleased to announce that the following papers have been accepted for presentation at the Conference. For an accepted paper to be included in the proceedings, one of the authors must commit to presenting the paper at the conference.

Causal closure for MSC languages
B. Adsul, M. Mukund, K.N. Kumar, V. Narayanan

The directed planar reachability problem
E. Allender, S. Datta, S. Roy

Non-disclosure for distributed and mobile code
A. Almeida Matos

Proofs of the termination of rewrite rules for polytime functions
T. Arai, G. Moser

Probabilistic analysis for a multiple depot vehicle routing problem
A. Baltz, D. Dubhashi, A. Srivastav, L. Tansini, S. Werth

When are timed automata weakly timed bisimilar to time Petri nets ?
B. Berard, F. Cassez, S. Haddad, D. Lime, O.H. Roux

Improved bounds for the union complexity of fat objects
M. de Berg

Reachability analysis of multithreaded software with asynchronous communication
A. Bouajjani, J. Esparza, S. Schwoon, J. Strejcek

On the expressiveness of TPTL and MTL
P. Bouyer, F. Chevalier, N. Markey

Computing the expected accumulated reward and gain for a subclass of infinite Markov chains
T. Brazdil, A. Kucera

On the bisimulation congruence in chi calculus
T. Chen, T. Han, J. Lu

Market equilibrium for CES exchange economies: existence, multiplicity, and computation
B. Codenotti, B. McCune, S. Penumatcha, K. Varadarajan

Quantitative models and implicit complexity
U. Dal Lago, M. Hofmann

Reasoning about quantum knowledge
E. D'Hondt, P. Panangaden

Eventual timed automata
D. D'Souza, M. Raj Mohan

No coreset, no cry: 2
M. Edwards, K. Varadarajan

The equivalence problem for deterministic MSO tree transducers is decidable
J. Engelfriet, S. Maneth

Comparing trees via crossing minimization
H. Fernau, M. Kaufmann, M. Poths

Bisimulation quantified logics: undecidability
T. French

Practical algorithms for tracking database join sizes
S. Ganguly, D. Kesh, C. Saha

Fixpoint logics over hierarchical structures
S. Goeller, M. Lohrey

Dimensions of Copeland-Erdos sequences
X. Gu, J.H. Lutz, P. Moser

The set cover with pairs problem
R. Hassin, D. Segev

Extending Howe's method to early bisimulations for typed mobile embedded resources with local names
T. Hildebrandt, J.C. Godskesen

Testing concurrent systems: an interpretation of intuitionistic logic
R. Jagadeesan, G. Nadathur, V. Saraswat

Logarithmic-time single deleter, multiple inserter wait-free queues and stacks
P. Jayanti, S. Petrovic

On sampled semantics of timed systems
P. Krcal, R. Pelanek

Decidability issues for weakly extended PRS
M. Kretinsky, V. Rehak, J. Strejcek

Modal strength reduction in quantified discrete duration calculus
S.N. Krishna, P.K. Pandya

Controller synthesis for finite-state Markov decision processes
A. Kucera, O. Strazovsky

Approximation algorithms for wavelength assignment
V. Kumar, A. Rudra

The MSO theory of connectedly communicating processes
P. Madhusudan, P.S. Thiagarajan, S. Yang

Subquadratic algorithms for workload-aware Haar wavelet synopses
S. Muthukrishnan

Refining the undecidability frontier of hybrid automata
V. Mysore, A. Pnueli

Monitoring stable properties in dynamic peer-to-peer distributed systems
S. Peri, N. Mittal

Towards a CTL* tableau
M. Reynolds

On counting the number of consistent genotype assignments for pedigrees
J. Srba

Decision procedures for queues with integer constraints
T. Zhang, H.B. Sipma, Z. Manna


For all organization information related to the conference, like registration, accommodation, venue etc, please visit FSTTCS 2005, Hyderabad . For email correspondence with the organizers, contact:
fsttcs05 AT iiit DOT ac DOT in

Other events

4-8 December: 11th Asiacrypt Conference, Chennai, India
10-12 December: 6th Indocrypt Conference, Bangalore, India
15-18 December: 25th FSTTCS Conference, Hyderabad, India
18-21 December: 12th HiPC Conference, Goa, India
19-21 December: 16th ISAAC Symposium, Sanya, Hainan, China
20-22 December: 2nd IICAI Conference, Pune, India
20-22 December: 12th COMAD Conference, Hyderabad, India
22-24 December: 2nd ICDCIT Conference, Bhubaneswar, India
27-30 December: 7th IWDC Workshop, Kharagpur, India


The conference proceedings will be published by Springer in its Lecture Notes in Computer Science (LNCS) series as LNCS 3821. The proceedings of the 2004 conference was published as LNCS 3328.

Guidelines for Authors

The final camera-ready copy of accepted papers is due on September 16. The camera-ready version is limited to 12 pages in LNCS style. Detailed instructions for authors for preparing and sending the manuscript are available here.

For an accepted paper to be included in the proceedings, one of the authors must commit to presenting the paper at the conference.

Programme Committee

Luca Aceto , Aalborg U/ Reykjavik U
Mike Atallah, Purdue U
Anuj Dawar, Cambridge U
Paul Gastin, ENS Cachan
Dimitra Giannakopoulou, NASA Ames
Sudipto Guha, U Penn
Venkatesan Guruswami, U Washington
Sariel Har-Peled, UIUC
Samir Khuller, U Maryland
Amit Kumar, IIT Delhi
Kamal Lodaya, IMSc Chennai
P. Madhusudan, UIUC
Yossi Matias, Tel Aviv U
Anca Muscholl, LIAFA Paris
Tobias Nipkow, TU München
Greg Plaxton, UT Austin
Sanjiva Prasad, IIT Delhi
Jaikumar Radhakrishnan, TIFR Mumbai
G. Ramalingam, IBM Research
Rajeev Raman, U Leicester
R. Ramanujam, IMSc Chennai (co-chair)
Mark Reynolds, UWA Perth
Sandeep Sen, IIT Kharagpur (co-chair)
Santosh Vempala, MIT Cambridge



Email: fsttcs05 AT iiit DOT ac DOT in
Phone: +91 40 2300 1967 / +91 40 2300 1969
Fax: +91 40 2300 1413 (Mark "ATTN: Prosenjit Gupta")
URLs: Local Arrangements Site 1,
Local Arrangements Site 2,
Local Arrangements Site 3

Postal address: FSTTCS 05 Organization
ATTN: Prosenjit Gupta
International Institute of Information Technology,
Gachibowli, Hyderabad 500 032, INDIA


Email: fsttcs AT imsc DOT res DOT in
Phone: +91 44 2254 1856
Fax: +91 44 2254 1586
URL: www.fsttcs.org

Postal address: FSTTCS 05,
The Institute of Mathematical Sciences,
CIT Campus,
Chennai 600 113, INDIA

Important Dates

Notification to Authors: 19 August 2005
Final Version of Accepted Papers due on: 16 September 2005
Workshops: 12-14 December 2005
Conference: 15-18 December 2005

FSTTCS is the annual conference of IARCS, the Indian Association for Research in Computing Science.

Last update: 2 December 05