FSTTCS 2005 Programme

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

December 15--18, 2005
International Institute of Information Technology
Hyderabad, INDIA
Four full days: seven invited talks, seven sessions of contributed papers. A special session and a rump session.

Day 1 (15 December 2005, Thursday)
8:30am Registration
9:15am Opening Remarks
9:30am
Invited talk 		Chair: R. Ramanujam
Tom Henzinger, EPFL, Lausanne, and University of California at Berkeley
Semiperfect-Information Games
10:30am
 Tea
11:00am
Contributed papers
Parallel session 1A
Chair: K. V. Subrahmanyam 		Parallel session 1B
Chair: Madhavan Mukund
No Coreset, No Cry: 2
Michael Edwards, Kasturi Varadarajan

Improved Bounds for the Union Complexity of Fat Objects
M. de Berg

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

Extending Howe's Method to Early Bisimulations for Typed Mobile Embedded Resources with Local Names
T. Hildebrandt and J. C. Godskesen

11:50am Break
12:00pm
Contributed papers
Approximation Algorithms for Wavelength Assignment
V. Kumar and A. Rudra

The Set Cover with Pairs Problem
R. Hassin and D. Segev

Non-disclosure for distributed mobile code
A. Almeida Matos

Quantitative Models and Implicit Complexity
Dal Lago, U. and Hofmann, M.

12:50pm Lunch
2:30pm
Invited talk		 Chair: Venkatesan Guruswami
Russell Impagliazzo, University of California at San Diego
Computational Complexity Since 1980
3:30pm Tea
4:00pm
Contributed papers
Session 2
Chair: G. Ramalingam
The MSO Theory of Connectedly Communicating Processes
P. Madhusudan, P.S. Thiagarajan, S. Yang

Reachability of Hennessy-Milner Properties for Weakly Extended PRS
M. Kretinsky, V. Rehak, J. Strejcek

Decision Procedures for Queues with Integer Constraints
Ting Zhang, Henny B. Sipma, Zohar Manna


Day 2 (16 December 2005, Friday)
9:00am
Invited talk 		Chair: Sandeep Sen
Raimund Seidel, Universitaet Saarlandes, Saarbruecken, and University of California at Berkeley
Data Structures Research during the First 25 Years of FSTTCS
10:00am
 Tea
10:30am
Contributed papers
Parallel session 3A
Chair: Subir Ghosh 		Parallel session 3B
Chair: Mark Reynolds
The Directed Planar Reachability Problem
E. Allender, S. Datta, S. Roy

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

Refining The Undecidability Frontier Of Hybrid Automata
V. Mysore and A. Pnueli

When are Timed Automata weakly timed bisimilar to Time Petri Nets ?
B. Berard, F. Cassez, S. Haddad, Didier Lime, O.H.Roux

11:20am Break
11:30am
Contributed papers
Subquadratic Algorithms for Workload-Aware Haar Wavelet Synopses
S. Muthukrishnan

Practical Algorithms for Tracking Database Join Sizes
S. Ganguly, D. Kesh, C. Saha

On Sampled Semantics of Timed Systems
P. Krcal and R. Pelanek

Eventual Timed Automata
Deepak D'Souza, Raj Mohan M

12:20pm Lunch
2:00pm
Invited talk		 Chair: Sanjiva Prasad
Natarajan Shankar, SRI
Logical Algorithms
3:00pm Tea
3:20pm
Contributed papers
Session 4
Chair: Anca Muscholl
Causal Closure for MSC Languages
B. Adsul, M. Mukund, K. N. Kumar, V. Narayanan

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

4:10pm Break
4:30pm
5:00pm
Sponsors' Presentations
Cultural Programme


Day 3 (17 December 2005, Saturday)
9:00am
Invited talk 		Chair: Kamal Lodaya
Igor Walukiewicz, LaBRI , Université Bordeaux
From logic to games
10:00am
 Tea
10:30am
Contributed papers
Parallel session 5A
Chair: Sudeb Pal 		Parallel session 5B
Chair: P. Madhusudan
Probabilistic Analysis for a Multiple Depot Vehicle Routing Problem
A. Baltz, D. Dubhashi, A. Srivastav, L. Tansini, S. Werth

Computing the Expected Accumulated Reward and Gain for a Subclass of Infinite Markov Chains
T. Brazdil, A. Kucera

Towards a CTL* Tableau
Mark Reynolds

Bisimulation quantified logics: undecidability
Tim French

11:20am Break
11:30am
Contributed papers
Logarithmic-Time Single Deleter, Multiple Inserter Wait-Free Queues and Stacks
P. Jayanti and S. Petrovic

Monitoring Stable Properties in Dynamic Peer-to-Peer Distributed Systems
Sathya Peri, Neeraj Mittal

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

Modal Strength Reduction in Quantified Discrete Duration Calculus
S.N.Krishna, P.K.Pandya

12:20pm Lunch
2:00pm
Invited talk		 Chair: Jaikumar Radhakrishnan
Manindra Agrawal, Indian Institute of Technology Kanpur
Proving Lower Bounds via Pseudo-Random Generators
3:00pm Tea
3:30pm
IARCS Commemorative Session on 25 years of FST&TCS
Chairs: Mathai Joseph and R.K. Shyamasundar
5:00pm
7:00pm
IARCS Business Meeting
Banquet


Day 4 (18 December 2005, Sunday)
9:00am
Invited talk 		Chair: Sariel Har-Peled
Joel Spencer, New York University
Erdos Magic
10:00am
 Tea
10:30am
Contributed papers
Parallel session 6A
Chair: Venkatesh Raman 		Parallel session 6B
Chair: Paritosh Pandya
Comparing trees via crossing minimization
H Fernau, M Kaufmann, M Poths

On Counting the Number of Consistent Genotype Assignments for Pedigrees
J. Srba

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

The Equivalence Problem for Deterministic MSO Tree Transducers is Decidable
J. Engelfriet and S. Maneth

11:20am Break
11:30am
Contributed papers
Market Equilibrium for CES Exchange Economies: Existence, Multiplicity, and Computation
B. Codenotti, B. McCune, S. Penumatcha, K. Varadarajan 		Testing concurrent systems: an interpretation of intuitionistic logic
Radha Jagadeesan, Gopalan Nadathur, Vijay Saraswat

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

12:20pm Lunch
1:30pm
Contributed papers
Session 7
Chair: Anil Seth
Controller Synthesis for Finite-State Markov Decision Processes
A. Kucera and O. Strazovsky

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

2:20-3:20pm Rump Session
3:20pm Closing remarks
3:30pm Tea