Mathematical Foundations of Computer Science 2004: 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings

Front Matter....Pages -
A Case Study of Genome Evolution: From Continuous to Discrete Time Model....Pages 1-24
Multicoloring: Problems and Techniques....Pages 25-41
Some Recent Progress in Algorithmic Randomness....Pages 42-83
Ubiquitous Parameterization — Invitation to Fixed-Parameter Algorithms....Pages 84-103
PRAM-On-Chip: A Quest for Not-So-Obvious Non-obviousness....Pages 104-105
Theory and Applied Computing: Observations and Anecdotes....Pages 106-118
Boxed Ambients with Communication Interfaces....Pages 119-148
Algebraic Recognizability of Languages....Pages 149-175
Geometric Optimization and Unique Sink Orientations of Cubes....Pages 176-176
Congestion Games and Coordination Mechanisms....Pages 177-179
Equitable Colorings of Bounded Treewidth Graphs....Pages 180-190
The Bidimensional Theory of Bounded-Genus Graphs....Pages 191-203
Parallel Knock-Out Schemes in Networks....Pages 204-214
Online Algorithms for Disk Graphs....Pages 215-226
Protein Folding in the HP Model on Grid Lattices with Diagonals....Pages 227-238
Optimization, Games, and Quantified Constraint Satisfaction....Pages 239-250
Approximating Boolean Functions by OBDDs....Pages 251-262
On Approximation Hardness of the Minimum 2SAT-DELETION Problem....Pages 263-273
Group Coloring and List Group Coloring Are Π 2 P -Complete....Pages 274-286
Complexity Results in Graph Reconstruction....Pages 287-297
Generating Paths and Cuts in Multi-pole (Di)graphs....Pages 298-309
Packing Directed Cycles Efficiently....Pages 310-321
The Complexity of Membership Problems for Circuits over Sets of Integers....Pages 322-333
Some Meet-in-the-Middle Circuit Lower Bounds....Pages 334-345
The Enumerability of P Collapses P to NC....Pages 346-355
On NC 1 Boolean Circuit Composition of Non-interactive Perfect Zero-Knowledge....Pages 356-367
All Superlinear Inverse Schemes Are coNP-Hard....Pages 368-379
The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups....Pages 380-391
Generation Problems....Pages 392-403
One Query Reducibilities Between Partial Information Classes....Pages 404-415
A New Dimension Sensitive Property for Cellular Automata....Pages 416-426
Captive Cellular Automata....Pages 427-438
Simulating 3D Cellular Automata with 2D Cellular Automata....Pages 439-450
Graph Exploration by a Finite Automaton....Pages 451-462
On Polynomially Time Bounded Symmetry of Information....Pages 463-475
Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets....Pages 476-487
A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs....Pages 488-499
Polynomial Time Approximation Schemes and Parameterized Complexity....Pages 500-512
Epistemic Foundation of the Well-Founded Semantics over Bilattices....Pages 513-524
Structural Model Checking for Communicating Hierarchical Machines....Pages 525-536
Compositional Verification: Decidability Issues Using Graph Substitutions....Pages 537-549
Event Structures for Resolvable Conflict....Pages 550-561
Optimal Preemptive Scheduling for General Target Functions....Pages 562-573
The Price of Anarchy for Polynomial Social Cost....Pages 574-585
Agent-Based Information Handling in Large Networks....Pages 586-598
Approximating Earliest Arrival Flows with Flow-Dependent Transit Times....Pages 599-610
A Hierarchy of Irreducible Sofic Shifts....Pages 611-622
Membership and Reachability Problems for Row-Monomial Transformations....Pages 623-634
On Pseudovarieties of Semiring Homomorphisms....Pages 635-647
An Algebraic Generalization of ω -Regular Languages....Pages 648-659
A Protocol for Serializing Unique Strategies....Pages 660-672
A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games....Pages 673-685
When Can You Play Positionally?....Pages 686-697
The Dual of Concatenation....Pages 698-710
Computational Aspects of Disjunctive Sequences....Pages 711-722
Decidability of Trajectory-Based Equations....Pages 723-734
Efficient View Point Selection for Silhouettes of Convex Polyhedra....Pages 735-747
Angles and Lengths in Reconfigurations of Polygons and Polyhedra....Pages 748-759
Improved Bounds and Schemes for the Declustering Problem....Pages 760-771
Crossing Number Is Hard for Cubic Graphs....Pages 772-782
A Reducibility for the Dot-Depth Hierarchy....Pages 783-793
Sublogarithmic Ambiguity....Pages 794-806
An Elementary Proof for the Non-parametrizability of the Equation xyz = zvx ....Pages 807-817
A Generalization of Repetition Threshold....Pages 818-826
An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation....Pages 827-838
Universal Test for Quantum One-Way Permutations....Pages 839-850
A Common Algebraic Description for Probabilistic and Quantum Computations....Pages 851-862
Extraction and Implication of Path Constraints....Pages 863-875
Schema Evolution for XML: A Consistency-Preserving Approach....Pages 876-888
Complexity of Decision Problems for Simple Regular Expressions....Pages 889-900
Back Matter....Pages -