Mathematical Foundations of Computer Science 2002

Invited Talks.- Global Development via Local Observational Construction Steps.- Edge-Colouring Pairs of Binary Trees: Towards a Concise Proof of the Four-Colour Theorem of Planar Maps.- Applications of Finite Automata.- Approximability of the Minimum Bisection Problem: An Algorithmic Challenge.- Low Stretch Spanning Trees.- Contributed Talks.- On Radiocoloring Hierarchically Specified Planar Graphs: -Completeness and Approximations.- Finite Domain Constraint Satisfaction Using Quantum Computation.- Fast Algorithms with Algebraic Monge Properties.- Packing Edges in Random Regular Graphs.- A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications.- Matroid Intersections, Polymatroid Inequalities, and Related Problems.- Accessibility in Automata on Scattered Linear Orderings.- On Infinite Terms Having a Decidable Monadic Theory.- A Chomsky-Like Hierarchy of Infinite Graphs.- Competitive Analysis of On-line Stream Merging Algorithms.- Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming.- On Word Equations in One Variable.- Autoreducibility of Random Sets: A Sharp Bound on the Density of Guessed Bits.- Two-Way Finite State Transducers with Nested Pebbles.- Optimal Non-preemptive Semi-online Scheduling on Two Related Machines.- More on Weighted Servers or Fifo is Better than Lru.- On Maximizing the Throughput of Multiprocessor Tasks.- Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures.- Evolutive Tandem Repeats Using Hamming Distance.- Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth.- Computing Partial Information out of Intractable One - The First Digit of 2n at Base 3 as anExample.- Algorithms for Computing Small NFAs.- Space-Economical Construction of Index Structures for All Suffixes of a String.- An Explicit Lower Bound of 5n ? o(n) for Boolean Circuits.- Computational Complexity in the Hyperbolic Plane.- On a Mereological System for Relational Software Specifications.- An Optimal Lower Bound for Resolution with 2-Conjunctions.- Improved Parameterized Algorithms for Planar Dominating Set.- Optimal Free Binary Decision Diagrams for Computation of EARn.- Unification Modulo Associativity and Idempotency Is NP-complete.- On the Complexity of Semantic Equivalences for Pushdown Automata and BPA.- An Improved Algorithm for the Membership Problem for Extended Regular Expressions.- Efficient Algorithms for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecular Sequence Analysis.- Derivation of Rational Expressions with Multiplicity.- Hypothesis-Founded Semantics for Datalog Programs with Negation.- On the Problem of Scheduling Flows on Distributed Networks.- Unit Testing for Casl Architectural Specifications.- Symbolic Semantics and Analysis for Crypto-CCS with (Almost) Generic Inference Systems.- The Complexity of Tree Multicolorings.- On Verifying Fair Lossy Channel Systems.- Parameterized Counting Problems.- On the Construction of Effective Random Sets.- On the Structure of the Simulation Order of Proof Systems.- Comorphism-Based Grothendieck Logics.- Finite Test-Sets for Overlap-Free Morphisms.- Characterizing Simpler Recognizable Sets of Integers.- Towards a Cardinality Theorem for Finite Automata.- An Approximation Semantics for the Propositional Mu-Calculus.