18. FSTTCS 1998: Chennai, India

Invited Talk 1

• Neil Immerman:
  Descriptive Complexity and Model Checking. 1-5
  

Session 1(a)

• Nili Guttmann-Beck, Refael Hassin, Samir Khuller, Balaji Raghavachari:
  Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem. 6-17
  
• Dimitris Fotakis, Paul G. Spirakis:
  A Hamiltonian Approach to the Assignment of Non-reusable Frequencies. 18-29
  

Session 1 (b)

• Carolina Lavatelli:
  Deadlock Sensitive Types for Lambda Calculus with Resources. 30-41
  
• Paola Quaglia, David Walker:
  On Encoding p-pi in m-pi. 42-53

Session 2 (a)

• Sudipto Guha, Samir Khuller:
  Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets. 54-65
  
• Mahesh Kallahalla, Peter J. Varman:
  Red-Black Prefetching: An Approximation Algorithm for Parallel Disk Scheduling. 66-77
  

Session 2 (b)

• Jean-Pierre Talpin, David Nowak:
  A Synchronous Semantics of Higher-Order Processes for Modeling Reconfigurable Reactive Systems. 78-89
  
• Ilaria Castellani, Matthew Hennessy:
  Testing Theories for Asynchronous Languages. 90-101
  

Invited Talk 2

• John H. Reif:
  Alternative Computational Models: A Comparison of Biomolecular and Quantum Computation. 102-121
  

Session 3

• Maya Madhavan, Priti Shankar:
  Optimal Regular Tree Pattern Matching Using Pushdown Automata. 122-133
  
• Andreas Neumann, Helmut Seidl:
  Locating Matches of Tree Patterns in Forests. 134-145
  

Session 4

• Armin Kühnemann:
  Benefits of Tree Transducers for Optimizing Functional Programs. 146-157
  
• Vijay K. Garg, J. Roger Mitchell:
  Implementable Failure Detectors in Asynchronous Systems. 158-169
  

Invited Talk 3

• Erik Meineche Schmidt:
  BRICS and Quantum Information Processing. 170-173
  

Session 5 (a)

• Devdatt P. Dubhashi:
  Martingales and Locality in Distributed Computing. 174-185
  
• J. Ian Munro, Venkatesh Raman, S. Srinivasa Rao:
  Space Efficient Suffix Trees. 186-196
  

Session 5 (b)

• N. S. Pendharkar, K. Gopinath:
  Formal Verification of an O. S. Submodule. 197-208
  
• K. Narayan Kumar, Rance Cleaveland, Scott A. Smolka:
  Infinite Probabilistic and Nonprobabilistic Testing. 209-220
  

Session 6 (a)

• N. Kalyana Rama Prasad, P. Sreenivasa Kumar:
  On Generating Strong Elimination Orderings of Strongly Chordal Graphs. 221-232
  
• Joachim Gudmundsson, Christos Levcopoulos:
  A Parallel Approximation Algorithm for Minimum Weight Triangulation. 233-244
  

Session 6 (b)

• Luca Aceto, Patricia Bouyer, Augusto Burgueño, Kim Guldstrand Larsen:
  The Power of Reachability Testing for Timed Automata. 245-256
  
• Paritosh K. Pandya, Y. S. Ramakrishna:
  Recursive Mean-Value Calculus. 257-268
  

Invited Talk 4

• Rajeev Alur:
  Efficient Formal Verification of Hierarchical Descriptions. 269
  

Invited Talk 5

• Kenneth L. McMillan:
  Proof Rules for Model Checking Systems with Data. 270
  

Session 7

• Michaela Huhn, Peter Niebert, Heike Wehrheim:
  Partial Order Reductions for Bisimulation Checking. 271-282
  
• Jürgen Bohn, Werner Damm, Orna Grumberg, Hardi Hungar, Karen Laster:
  First-Order-CTL Model Checking. 283-294
  

Session 8 (a)

• Antoni Lozano, Vijay Raghavan:
  On the Complexity of Counting the Number of Vertices Moved by Graph Automorphisms. 295-306
  
• Satyanarayana V. Lokam:
  Remarks on Graph Complexity. 307-318
  

Session 8 (b)

• Markus Lohrey:
  On the Confluence of Trace Rewriting Systems. 319-330
  
• Hugues Calbrix, Teodor Knapik:
  A String-Rewriting Characterization of Muller and Schupp's Context-Free Graphs. 331-342
  

Session 9

• Petr Jancar, Frantisek Mráz, Martin Plátek, Jörg Vogel:
  Different Types of Monotonicity for Restarting Automata. 343-354
  
• Kamal Lodaya, Pascal Weil:
  A Kleene Iteration for Parallelism. 355-366
  

Invited Talk 6

• Umesh V. Vazirani:
  Quantum Computation and Information. 367