Mathematical Foundations of Computer Science 2002

1. Front Matter

   Pages I-XII

   PDF

2. Invited Talks

   1. Global Development via Local Observational Construction Steps

      • Michel Bidoit, Donald Sannella, Andrzej Tarlecki

      Pages 1-24

   2. Edge-Colouring Pairs of Binary Trees: Towards a Concise Proof of the Four-Colour Theorem of Planar Maps

      • Alan Gibbons, Paul Sant

      Pages 25-39

   3. Applications of Finite Automata

      • Juhani Karhumäki

      Pages 40-58

   4. Approximability of the Minimum Bisection Problem: An Algorithmic Challenge

      • Marek Karpinski

      Pages 59-67

   5. Low Stretch Spanning Trees

      • David Peleg

      Pages 68-80

3. Contributed Talks

   1. On Radiocoloring Hierarchically Specified Planar Graphs: \( \mathcal{P}\mathcal{S}\mathcal{P}\mathcal{A}\mathcal{C}\mathcal{E} \) -Completeness and Approximations

      • Maria I. Andreou, Dimitris A. Fotakis, Sotiris E. Nikoletseas, Vicky G. Papadopoulou, Paul G. Spirakis

      Pages 81-92

   2. Finite Domain Constraint Satisfaction Using Quantum Computation

      • Ola Angelsmark, Vilhelm Dahllöf, Peter Jonsson

      Pages 93-103

   3. Fast Algorithms with Algebraic Monge Properties

      • Wolfgang W. Bein, Peter Brucker, Lawrence L. Larmore, James K. Park

      Pages 104-117

   4. Packing Edges in Random Regular Graphs

      • Mihalis Beis, William Duckworth, Michele Zito

      Pages 118-130

   5. A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications

      • Beate Bollig, Philipp Woelfel

      Pages 131-142

   6. Matroid Intersections, Polymatroid Inequalities, and Related Problems

      • Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan

      Pages 143-154

   7. Accessibility in Automata on Scattered Linear Orderings

      • Olivier Carton

      Pages 155-164

   8. On Infinite Terms Having a Decidable Monadic Theory

      • Didier Caucal

      Pages 165-176

   9. A Chomsky-Like Hierarchy of Infinite Graphs

      • Didier Caucal, Teodor Knapik

      Pages 177-187

   10. Competitive Analysis of On-line Stream Merging Algorithms

       • Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, Prudence W. H. Wong

       Pages 188-200

   11. Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming

       • Amin Coja-Oghlan

       Pages 201-211

   12. On Word Equations in One Variable

       • Robert Dabrowski, Wojtek Plandowski

       Pages 212-220

   13. Autoreducibility of Random Sets: A Sharp Bound on the Density of Guessed Bits

       • Todd Ebert, Wolfgang Merkle

       Pages 221-233

   14. Two-Way Finite State Transducers with Nested Pebbles

       • Joost Engelfriet, Sebastian Maneth

       Pages 234-244

This book constitutes the refereed proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science, MFCS 2002, held in Warsaw, Poland in August 2002.
The 48 revised full papers presented together with 5 invited papers were carefully reviewed and selected from 108 submissions. All relevant aspects of theoretical computer science are addressed, ranging from discrete mathematics, combinatorial optimization, graph theory, algorithms, and complexity to programming theory, formal methods, and mathematical logic.

• algorithms
• combinatorial optimization
• complexity
• computer
• computer science
• formal method
• logic
• mathematical logic
• optimization
• programming
• data structures

• Institute of Informatics, Warsaw University, Warszawa, Poland

  Krzysztof Diks, Wojciech Rytter

• Department of Computer Science, Liverpool University, Liverpool, UK

  Wojciech Rytter

Policies and ethics