25. FSTTCS 2005: Hyderabad, India

Invited Papers

• Krishnendu Chatterjee, Thomas A. Henzinger:
  Semiperfect-Information Games. 1-18
  
• Russell Impagliazzo:
  Computational Complexity Since 1980. 19-47
  
• Raimund Seidel:
  Developments in Data Structure Research During the First 25 Years of FSTTCS. 48-59
  
• Natarajan Shankar:
  Inference Systems for Logical Algorithms. 60-78
  
• Igor Walukiewicz:
  From Logic to Games. 79-91
  
• Manindra Agrawal:
  Proving Lower Bounds Via Pseudo-random Generators. 92-105
  
• Joel Spencer:
  Erdös Magic. 106
  

Contributed Papers

• Michael Edwards, Kasturi R. Varadarajan:
  No Coreset, No Cry: II. 107-115
  
• Mark de Berg:
  Improved Bounds on the Union Complexity of Fat Objects. 116-127
  
• Taolue Chen, Tingting Han, Jian Lu:
  On the Bisimulation Congruence in chi-Calculus. 128-139
  
• Jens Chr. Godskesen, Thomas T. Hildebrandt:
  Extending Howe's Method to Early Bisimulations for Typed Mobile Embedded Resources with Local Names. 140-151
  
• Vijay Kumar, Atri Rudra:
  Approximation Algorithms for Wavelength Assignment. 152-163
  
• Refael Hassin, Danny Segev:
  The Set Cover with Pairs Problem. 164-176
  
• Ana Almeida Matos:
  Non-disclosure for Distributed Mobile Code. 177-188
  
• Ugo Dal Lago, Martin Hofmann:
  Quantitative Models and Implicit Complexity. 189-200
  
• P. Madhusudan, P. S. Thiagarajan, Shaofa Yang:
  The MSO Theory of Connectedly Communicating Processes. 201-212
  
• Mojmír Kretínský, Vojtech Rehák, Jan Strejcek:
  Reachability of Hennessy-Milner Properties for Weakly Extended PRS. 213-224
  
• Ting Zhang, Henny B. Sipma, Zohar Manna:
  Decision Procedures for Queues with Integer Constraints. 225-237
  
• Eric Allender, Samir Datta, Sambuddha Roy:
  The Directed Planar Reachability Problem. 238-249
  
• Xiaoyang Gu, Jack H. Lutz, Philippe Moser:
  Dimensions of Copeland-Erdös Sequences. 250-260
  
• Venkatesh Mysore, Amir Pnueli:
  Refining the Undecidability Frontier of Hybrid Automata. 261-272
  
• Béatrice Bérard, Franck Cassez, Serge Haddad, Didier Lime, Olivier H. Roux:
  When Are Timed Automata Weakly Timed Bisimilar to Time Petri Nets? 273-284
  
• S. Muthukrishnan:
  Subquadratic Algorithms for Workload-Aware Haar Wavelet Synopses. 285-296
  
• Sumit Ganguly, Deepanjan Kesh, Chandan Saha:
  Practical Algorithms for Tracking Database Join Sizes. 297-309
  
• Pavel Krcál, Radek Pelánek:
  On Sampled Semantics of Timed Systems. 310-321
  
• Deepak D'Souza, M. Raj Mohan:
  Eventual Timed Automata. 322-334
  
• Bharat Adsul, Madhavan Mukund, K. Narayan Kumar, Vasumathi Narayanan:
  Causal Closure for MSC Languages. 335-347
  
• Ahmed Bouajjani, Javier Esparza, Stefan Schwoon, Jan Strejcek:
  Reachability Analysis of Multithreaded Software with Asynchronous Communication. 348-359
  
• Andreas Baltz, Devdatt P. Dubhashi, Libertad Tansini, Anand Srivastav, Sören Werth:
  Probabilistic Analysis for a Multiple Depot Vehicle Routing Problem. 360-371
  
• Tomás Brázdil, Antonín Kucera:
  Computing the Expected Accumulated Reward and Gain for a Subclass of Infinite Markov Chains. 372-383
  
• Mark Reynolds:
  Towards a CTL* Tableau. 384-395
  
• Tim French:
  Bisimulation Quantified Logics: Undecidability. 396-407
  
• Prasad Jayanti, Srdjan Petrovic:
  Logarithmic-Time Single Deleter, Multiple Inserter Wait-Free Queues and Stacks. 408-419
  
• Sathya Peri, Neeraj Mittal:
  Monitoring Stable Properties in Dynamic Peer-to-Peer Distributed Systems. 420-431
  
• Patricia Bouyer, Fabrice Chevalier, Nicolas Markey:
  On the Expressiveness of TPTL and MTL. 432-443
  
• Shankara Narayanan Krishna, Paritosh K. Pandya:
  Modal Strength Reduction in Quantified Discrete Duration Calculus. 444-456
  
• Henning Fernau, Michael Kaufmann, Mathias Poths:
  Comparing Trees Via Crossing Minimization. 457-469
  
• Jirí Srba:
  On Counting the Number of Consistent Genotype Assignments for Pedigrees. 470-482
  
• Stefan Göller, Markus Lohrey:
  Fixpoint Logics on Hierarchical Structures. 483-494
  
• Joost Engelfriet, Sebastian Maneth:
  The Equivalence Problem for Deterministic MSO Tree Transducers Is Decidable. 495-504
  
• Bruno Codenotti, Benton McCune, Sriram Penumatcha, Kasturi R. Varadarajan:
  Market Equilibrium for CES Exchange Economies: Existence, Multiplicity, and Computation. 505-516
  
• Radha Jagadeesan, Gopalan Nadathur, Vijay A. Saraswat:
  Testing Concurrent Systems: An Interpretation of Intuitionistic Logic. 517-528
  
• Toshiyasu Arai, Georg Moser:
  Proofs of Termination of Rewrite Systems for Polytime Functions. 529-540
  
• Antonín Kucera, Oldrich Strazovský:
  On the Controller Synthesis for Finite-State Markov Decision Processes. 541-552
  
• Ellie D'Hondt, Prakash Panangaden:
  Reasoning About Quantum Knowledge. 553-564