Ebook: Mathematical Foundations of Computer Science 2002: 27th International Symposium, MFCS 2002 Warsaw, Poland, August 26–30, 2002 Proceedings

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.

---

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.

---

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.
Content:
Front Matter....Pages I-XII
Global Development via Local Observational Construction Steps....Pages 1-24
Edge-Colouring Pairs of Binary Trees: Towards a Concise Proof of the Four-Colour Theorem of Planar Maps....Pages 25-39
Applications of Finite Automata....Pages 40-58
Approximability of the Minimum Bisection Problem: An Algorithmic Challenge....Pages 59-67
Low Stretch Spanning Trees....Pages 68-80
Finite Domain Constraint Satisfaction Using Quantum Computation....Pages 81-92
Fast Algorithms with Algebraic Monge Properties....Pages 93-103
Packing Edges in Random Regular Graphs....Pages 104-117
A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications....Pages 118-130
Matroid Intersections, Polymatroid Inequalities, and Related Problems....Pages 131-142
Accessibility in Automata on Scattered Linear Orderings....Pages 143-154
On Infinite Terms Having a Decidable Monadic Theory....Pages 155-164
A Chomsky-Like Hierarchy of Infinite Graphs....Pages 165-176
Competitive Analysis of On-line Stream Merging Algorithms....Pages 177-187
Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming....Pages 188-200
On Word Equations in One Variable....Pages 201-211
Autoreducibility of Random Sets: A Sharp Bound on the Density of Guessed Bits....Pages 212-220
Two-Way Finite State Transducers with Nested Pebbles....Pages 221-233
Optimal Non-preemptive Semi-online Scheduling on Two Related Machines....Pages 234-244
On Maximizing the Throughput of Multiprocessor Tasks....Pages 245-256
Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures....Pages 257-268
Evolutive Tandem Repeats Using Hamming Distance....Pages 269-279
Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth....Pages 280-291
Computing Partial Information out of Intractable One — The First Digit of 2n at Base 3 as an Example....Pages 292-304
Algorithms for Computing Small NFAs....Pages 305-318
Space-Economical Construction of Index Structures for All Suffixes of a String....Pages 319-327
An Explicit Lower Bound of 5n ? o(n) for Boolean Circuits....Pages 328-340
Computational Complexity in the Hyperbolic Plane....Pages 341-352
On a Mereological System for Relational Software Specifications....Pages 353-364
An Optimal Lower Bound for Resolution with 2-Conjunctions....Pages 365-374
Improved Parameterized Algorithms for Planar Dominating Set....Pages 375-386
Unification Modulo Associativity and Idempotency Is NP-complete....Pages 387-398
On the Complexity of Semantic Equivalences for Pushdown Automata and BPA....Pages 399-410
An Improved Algorithm for the Membership Problem for Extended Regular Expressions....Pages 411-422
Efficient Algorithms for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecular Sequence Analysis....Pages 423-432
Derivation of Rational Expressions with Multiplicity....Pages 433-445
Hypothesis-Founded Semantics for Datalog Programs with Negation....Pages 446-458
On the Problem of Scheduling Flows on Distributed Networks....Pages 459-470
Unit Testing for Casl Architectural Specifications....Pages 471-482
Symbolic Semantics and Analysis for Crypto-CCS with (Almost) Generic Inference Systems....Pages 483-494
The Complexity of Tree Multicolorings....Pages 495-505
On Verifying Fair Lossy Channel Systems....Pages 506-518
Parameterized Counting Problems....Pages 519-531
On the Construction of Effective Random Sets....Pages 532-542
On the Structure of the Simulation Order of Proof Systems....Pages 543-555
Comorphism-Based Grothendieck Logics....Pages 556-567
Finite Test-Sets for Overlap-Free Morphisms....Pages 568-580
Characterizing Simpler Recognizable Sets of Integers....Pages 581-592
Towards a Cardinality Theorem for Finite Automata....Pages 593-604
An Approximation Semantics for the Propositional Mu-Calculus....Pages 605-614
Back Matter....Pages 615-624
....Pages 625-636