27. MFCS 2002: Warsaw, Poland

Invited Talks

• Michel Bidoit, Donald Sannella, Andrzej Tarlecki:
  Global Development via Local Observational Construction Steps. 1-24
  
• Alan Gibbons, Paul Sant:
  Edge-Colouring Pairs of Binary Trees: Towards a Concise Proof of the Four-Colour Theorem of Planar Maps. 25-39
  
• Juhani Karhumäki:
  Applications of Finite Automata. 40-58
  
• Marek Karpinski:
  Approximability of the Minimum Bisection Problem: An Algorithmic Challenge. 59-67
  
• David Peleg:
  Low Stretch Spanning Trees. 68-80
  

Contributed Talks

• Maria I. Andreou, Dimitris Fotakis, Sotiris E. Nikoletseas, Vicky G. Papadopoulou, Paul G. Spirakis:
  On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-Completeness and Approximations. 81-92
  
• Ola Angelsmark, Vilhelm Dahllöf, Peter Jonsson:
  Finite Domain Constraint Satisfaction Using Quantum Computation. 93-103
  
• Wolfgang W. Bein, Peter Brucker, Lawrence L. Larmore, James K. Park:
  Fast Algorithms with Algebraic Monge Properties. 104-117
  
• Mihalis Beis, William Duckworth, Michele Zito:
  Packing Edges in Random Regular Graphs. 118-130
  
• Beate Bollig, Philipp Woelfel:
  A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications. 131-142
  
• Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan:
  Matroid Intersections, Polymatroid Inequalities, and Related Problems. 143-154
  
• Olivier Carton:
  Accessibility in Automata on Scattered Linear Orderings. 155-164
  
• Didier Caucal:
  On Infinite Terms Having a Decidable Monadic Theory. 165-176
  
• Didier Caucal, Teodor Knapik:
  A Chomsky-Like Hierarchy of Infinite Graphs. 177-187
  
• Wun-Tat Chan, Tak Wah Lam, Hing-Fung Ting, Prudence W. H. Wong:
  Competitive Analysis of On-line Stream Merging Algorithms. 188-200
  
• Amin Coja-Oghlan:
  Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming. 201-211
  
• Robert Dabrowski, Wojciech Plandowski:
  On Word Equations in One Variable. 212-220
  
• Todd Ebert, Wolfgang Merkle:
  Autoreducibility of Random Sets: A Sharp Bound on the Density of Guessed Bits. 221-233
  
• Joost Engelfriet, Sebastian Maneth:
  Two-Way Finite State Transducers with Nested Pebbles. 234-244
  
• Leah Epstein, Lene M. Favrholdt:
  Optimal Non-preemptive Semi-online Scheduling on Two Related Machines. 245-256
  
• Leah Epstein, Csanád Imreh, Rob van Stee:
  More on Weighted Servers or FIFO is Better than LRU. 257-268
  
• Aleksei V. Fishkin, Guochuan Zhang:
  On Maximizing the Throughput of Multiprocessor Tasks. 269-279
  
• Andreas Goerdt, Tomasz Jurdzinski:
  Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures. 280-291
  
• Richard Groult, Martine Léonard, Laurent Mouchard:
  Evolutive Tandem Repeats Using Hamming Distance. 292-304
  
• Mohammad Taghi Hajiaghayi, Naomi Nishimura:
  Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth. 305-318
  
• Mika Hirvensalo, Juhani Karhumäki:
  Computing Partial Information out of Intractable One - The First Digit of 2 ⁿ at Base 3 as an Example. 319-327
  
• Lucian Ilie, Sheng Yu:
  Algorithms for Computing Small NFAs. 328-340
  
• Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Hideo Bannai, Setsuo Arikawa:
  Space-Economical Construction of Index Structures for All Suffixes of a String. 341-352
  
• Kazuo Iwama, Hiroki Morizumi:
  An Explicit Lower Bound of 5n - o(n) for Boolean Circuits. 353-364
  
• Chuzo Iwamoto, Takeshi Andou, Kenichi Morita, Katsunobu Imai:
  Computational Complexity in the Hyperbolic Plane. 365-374
  
• Ryszard Janicki:
  On a Mereological System for Relational Software Specifications. 375-386
  
• Jan Johannsen, N. S. Narayanaswamy:
  An Optimal Lower Bound for Resolution with 2-Conjunctions. 387-398
  
• Iyad A. Kanj, Ljubomir Perkovic:
  Improved Parameterized Algorithms for Planar Dominating Set. 399-410
  
• Jan Kára, Daniel Král:
  Optimal Free Binary Decision Diagrams for Computation of EAR_n. 411-422
  
• Ondrej Klíma:
  Unification Modulo Associativity and Idempotency Is NP-complete. 423-432
  
• Antonín Kucera, Richard Mayr:
  On the Complexity of Semantic Equivalences for Pushdown Automata and BPA. 433-445
  
• Orna Kupferman, Sharon Zuhovitzky:
  An Improved Algorithm for the Membership Problem for Extended Regular Expressions. 446-458
  
• Yaw-Ling Lin, Tao Jiang, Kun-Mao Chao:
  Efficient Algorithms for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecular Sequence Analysis. 459-470
  
• Sylvain Lombardy, Jacques Sakarovitch:
  Derivation of Rational Expressions with Multiplicity. 471-482
  
• Yann Loyer, Nicolas Spyratos:
  Hypothesis-Founded Semantics for Datalog Programs with Negation. 483-494
  
• Thomas Lücking, Burkhard Monien, Manuel Rode:
  On the Problem of Scheduling Flows on Distributed Networks. 495-505
  
• Patrícia D. L. Machado, Donald Sannella:
  Unit Testing for C88 ASL Architectural Specifications. 506-518
  
• Fabio Martinelli:
  Symbolic Semantics and Analysis for Crypto-CCS with (Almost) Generic Inference Systems. 519-531
  
• Dániel Marx:
  The Complexity of Tree Multicolorings. 532-542
  
• Benoît Masson, Ph. Schnoebelen:
  On Verifying Fair Lossy Channel Systems. 543-555
  
• Catherine McCartin:
  Parameterized Counting Problems. 556-567
  
• Wolfgang Merkle, Nenad Mihailovic:
  On the Construction of Effective Random Sets. 568-580
  
• Jochen Messner:
  On the Structure of the Simulation Order of Proof Systems. 581-592
  
• Till Mossakowski:
  Comorphism-Based Grothendieck Logics. 593-604
  
• Gwénaël Richomme, Francis Wlazinski:
  Finite Test-Sets for Overlap-Free Morphisms. 605-614
  
• Michel Rigo:
  Characterizing Simpler Recognizable Sets of Integers. 615-624
  
• Till Tantau:
  Towards a Cardinality Theorem for Finite Automata. 625-636
  
• Roger Villemaire:
  An Approximation Semantics for the Propositional Mu-Calculus. 637-650