Mathematical Foundations of Computer Science 2002 Book

	Global Development via Local Observational Construction Steps	1
	Edge-Colouring Pairs of Binary Trees: Towards a Concise Proof of the Four-Colour Theorem of Planar Maps	25
	Applications of Finite Automata	40
	Approximability of the Minimum Bisection Problem: An Algorithmic Challenge	59
	Low Stretch Spanning Trees	68
	On Radiocoloring Hierarchically Specified Planar Graphs: PSP ACE-Completeness and Approximations	81
	Finite Domain Constraint Satisfaction Using Quantum Computation	93
	Fast Algorithms with Algebraic Monge Properties	104
	Packing Edges in Random Regular Graphs	118
	A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications	131
	Matroid Intersections, Polymatroid Inequalities, and Related Problems	143
	Accessibility in Automata on Scattered Linear Orderings	155
	On Infinite Terms Having a Decidable Monadic Theory	165
	A Chomsky-Like Hierarchy of Infinite Graphs	177
	Competitive Analysis of On-line Stream Merging Algorithms	188
	Coloring k-Colorable Semirandom Graphs in Polynomial Expected Time via Semidefinite Programming	201
	On Word Equations in One Variable	212
	Autoreducibility of Random Sets: A Sharp Bound on the Density of Guessed Bits	221
	Two-Way Finite State Transducers with Nested Pebbles	234
	Optimal Non-preemptive Semi-online Scheduling on Two Related Machines	245
	More on Weighted Servers or FIFO is Better than LRU	257
	On Maximizing the Throughput of Multiprocessor Tasks	269
	Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures	280
	Evolutive Tandem Repeats Using Hamming Distance	292
	Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth	305
	Computing Partial Information out of Intractable One - The First Digit of 2[superscript n] at Base 3 as an Example	319
	Algorithms for Computing Small NFAs	328
	Space-Economical Construction of Index Structures for All Suffixes of a String	341
	An Explicit Lower Bound of 5n - o(n) for Boolean Circuits	353
	Computational Complexity in the Hyperbolic Plane	365
	On a Mereological System for Relational Software Specifications	375
	An Optimal Lower Bound for Resolution with 2-Conjunctions	387
	Improved Parameterized Algorithms for Planar Dominating Set	399
	Optimal Free Binary Decision Diagrams for Computation of EAR[subscript n]	411
	Unification Modulo Associativity and Idempotency Is NP-complete	423
	On the Complexity of Semantic Equivalences for Pushdown Automata and BPA	433
	An Improved Algorithm for the Membership Problem for Extended Regular Expressions	446
	Efficient Algorithms for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecular Sequence Analysis	459
	Derivation of Rational Expressions with Multiplicity	471
	Hypothesis-Founded Semantics for Datalog Programs with Negation	483
	On the Problem of Scheduling Flows on Distributed Networks	495
	Unit Testing for CASL Architectural Specifications	506
	Symbolic Semantics and Analysis for Crypto-CCS with (Almost) Generic Inference Systems	519
	The Complexity of Tree Multicolorings	532
	On Verifying Fair Lossy Channel Systems	543
	Parameterized Counting Problems	556
	On the Construction of Effective Random Sets	568
	On the Structure of the Simulation Order of Proof Systems	581
	Comorphism-Based Grothendieck Logics	593
	Finite Test-Sets for Overlap-Free Morphisms	605
	Characterizing Simpler Recognizable Sets of Integers	615
	Towards a Cardinality Theorem for Finite Automata	625
	An Approximation Semantics for the Propositional Mu-Calculus	637
	Author Index	651