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

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
More on Weighted Servers or Fifo is Better than Lru ....Pages 245-256
On Maximizing the Throughput of Multiprocessor Tasks....Pages 257-268
Some Results on Random Unsatisfiable k -Sat Instances and Approximation Algorithms Applied to Random Structures....Pages 269-279
Evolutive Tandem Repeats Using Hamming Distance....Pages 280-291
Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth....Pages 292-304
Computing Partial Information out of Intractable One — The First Digit of 2 n at Base 3 as an Example....Pages 305-318
Algorithms for Computing Small NFAs....Pages 319-327
Space-Economical Construction of Index Structures for All Suffixes of a String....Pages 328-340
An Explicit Lower Bound of 5 n − o ( n ) for Boolean Circuits....Pages 341-352
Computational Complexity in the Hyperbolic Plane....Pages 353-364
On a Mereological System for Relational Software Specifications....Pages 365-374
An Optimal Lower Bound for Resolution with 2-Conjunctions....Pages 375-386
Improved Parameterized Algorithms for Planar Dominating Set....Pages 387-398
Optimal Free Binary Decision Diagrams for Computation of EAR n ....Pages 399-410
Unification Modulo Associativity and Idempotency Is NP-complete....Pages 411-422
On the Complexity of Semantic Equivalences for Pushdown Automata and BPA....Pages 423-432
An Improved Algorithm for the Membership Problem for Extended Regular Expressions....Pages 433-445
Efficient Algorithms for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecular Sequence Analysis....Pages 446-458
Derivation of Rational Expressions with Multiplicity....Pages 459-470
Hypothesis-Founded Semantics for Datalog Programs with Negation....Pages 471-482
On the Problem of Scheduling Flows on Distributed Networks....Pages 483-494
Unit Testing for Casl Architectural Specifications....Pages 495-505
Symbolic Semantics and Analysis for Crypto-CCS with (Almost) Generic Inference Systems....Pages 506-518
The Complexity of Tree Multicolorings....Pages 519-531
On Verifying Fair Lossy Channel Systems....Pages 532-542
Parameterized Counting Problems....Pages 543-555
On the Construction of Effective Random Sets....Pages 556-567
On the Structure of the Simulation Order of Proof Systems....Pages 568-580
Comorphism-Based Grothendieck Logics....Pages 581-592
Finite Test-Sets for Overlap-Free Morphisms....Pages 593-604
Characterizing Simpler Recognizable Sets of Integers....Pages 605-614
Towards a Cardinality Theorem for Finite Automata....Pages 615-624
An Approximation Semantics for the Propositional Mu-Calculus....Pages 625-636
....Pages 637-649