19. FSTTCS 1999: Chennai, India

Invited Talk 1

• Micha Sharir:
  Recent Developments in the Theory of Arrangements of Surfaces. 1-20
  

Session 1(a)

• Srinivas Aluru, Fatih Erdogan Sevilgen:
  Dynamic Compressed Hypertoctrees with Application to the N-Body Problem. 21-33
  
• Jeet Chaudhuri, Subhas C. Nandy:
  Largest Empty Rectangle among a Point Set. 34-46
  

Session 1(b)

• Philippe Herrmann:
  Renaming is Necessary in Timed Regular Expressions. 47-59
  
• Deepak D'Souza, P. S. Thiagarajan:
  Product Interval Automata: A Subclass of Timed Automata. 60-71
  

Session 2(a)

• Rolf Fagerberg:
  The Complexity of Rebalancing a Binary Serach Tree. 72-83
  
• Erik D. Demaine, J. Ian Munro:
  Fast Allocation and Deallocation with an Improved Buddy System. 84-96
  

Session 2(b)

• Christof Löding:
  Optimal Bounds for Transformations of omega-Automata. 97-109
  
• Thomas Wilke:
  CTL⁺ is Exponentially more Succinct than CTL. 110-121
  

Invited Talk 2

• Martín Abadi, Cédric Fournet, Georges Gonthier:
  A Top-Down Look at a Secure Message. 122-141
  

Session 3

• Jürgen Dix, Karl Schlechta:
  Explaining Updates by Minimal Sums. 142-154
  
• James J. Lu, Neil V. Murray, Erik Rosenthal:
  A Foundation for Hybrid Knowledge Bases. 155-167
  

Session 4

• David von Oheimb:
  Hoare Logic for Mutual Recursion and Local Variables. 168-180
  

Invited Talk 3

• Jean-Jacques Lévy, Luc Maranget:
  Explicit Substitutions and Programming Languages. 181-200
  

Session 5(a)

• Luca Becchetti, Miriam Di Ianni, Alberto Marchetti-Spaccamela:
  Approximation Algorithms for Routing and Call Scheduling in All-Optical Chains and Rings. 201-212
  
• Naveen Garg, Sachin Jain, Chaitanya Swamy:
  A Randomized Algorithm for Flow Shop Scheduling. 213-218
  

Session 5(b)

• Ilaria Castellani, Madhavan Mukund, P. S. Thiagarajan:
  Synthesizing Distributed Transition Systems from Global Specification. 219-231
  
• Supratik Mukhopadhyay, Andreas Podelski:
  Beyond Region Graphs: Symbolic Forward Analysis of Timed Automata. 232-244
  

Session 6

• Nicole Bidoit, Sandra de Amo:
  Implicit Temporal Query Languages: Towards Completeness. 245-257
  
• Matthias Baaz, Agata Ciabattoni, Christian G. Fermüller, Helmut Veith:
  On the Undecidability of some Sub-Classical First-Order Logics. 258-268
  

Invited Talk 4

• Lila Kari, Mark Daley, Greg Gloor, Rani Siromoney, Laura F. Landweber:
  How to Compute with DNA. 269-282
  

Session 7(a)

• L. Sunil Chandran:
  A High Girth Graph Construction and a Lower Bound for Hitting Set Size for Combinatorial Rectangles. 283-290
  
• Jörg Schwerdt, Michiel H. M. Smid, Ravi Janardan, Eric Johnson, Jayanth Majhi:
  Protecting Facets in Layered Manufacturing. 291-303
  

Session 7(b)

• Roberto M. Amadio, Gérard Boudol, Cédric Lhoussaine:
  The Receptive Distributed pi-Calculus (Extended Abstract). 304-315
  
• Zoltán Ésik, Satoshi Okawa:
  Series and Parallel Operations on Pomsets. 316-328
  

Session 8

• Achour Mostéfaoui, Michel Raynal:
  Unreliable Failure Detectors with Limited Scope Accuracy and an Application to Consensus. 329-340
  

Invited Talk 5

• Seinosuke Toda:
  Graph Isomorphism: Its Complexity and Algorithms (Abstract). 341
  

Session 9(a)

• Martin Sauerhoff:
  Computing with Restricted Nondeterminism: The Dependence of the OBDD Size on the Number of Nondeterministic Variables. 342-355
  
• Detlef Sieling:
  Lower Bounds for Linear Transformed OBDDs and FBDDs (Extende Abstract). 356-368
  

Session 9(b)

• Michael Huth:
  A Unifying Framework for Model Checking Labeled Kripke Structures, Modal Transition Systems and Interval Transition Systems. 369-380
  
• Flavio Corradini, Rocco De Nicola, Anna Labella:
  Graded Modalities and Resource Bisimulation. 381-393
  

Session 10(a)

• Christian Schindelhauer, Andreas Jakoby:
  The Non-Recursive Power of Erroneous Computation. 394-406
  
• Tomoyuki Yamakami:
  Analysis of Quantum Functions (Preliminary Version). 407-419
  

Session 10(b)

• Bernhard Heinemann:
  On Sets Growing Continously. 420-431
  
• Ron van der Meyden, Nikolay V. Shilov:
  Model Checking Knowledge and Time in Systems with Perfect Recall (Extended Abstract). 432-445
  

FST&TCS - ISAAC Joint Session Talks

• Kurt Mehlhorn:
  The Engineering of some Bipartite Matching Programs. 446-449