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.
Author(s): Michel Bidoit, Donald Sannella, Andrzej Tarlecki (auth.), Krzysztof Diks, Wojciech Rytter (eds.)
Series: Lecture Notes in Computer Science 2420
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2002
Language: English
Pages: 660
Tags: Theory of Computation; Discrete Mathematics in Computer Science; Programming Languages, Compilers, Interpreters; Computer Graphics; Data Structures
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
