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

Jerzy Tiuryn, Ryszard Rudnicki, Damian Wójtowicz (auth.), Jiří Fiala, Václav Koubek, Jan Kratochvíl (eds.)3540228233, 9783540228233, 9783540286295

This volume contains the papers presented at the 29th Symposium on Mat- matical Foundations of Computer Science, MFCS 2004, held in Prague, Czech Republic, August 22–27, 2004. The conference was organized by the Institute for Theoretical Computer Science (ITI) and the Department of Theoretical Com- terScienceandMathematicalLogic(KTIML)oftheFacultyofMathematicsand Physics of Charles University in Prague. It was supported in part by the Eu- pean Association for Theoretical Computer Science (EATCS) and the European Research Consortium for Informatics and Mathematics (ERCIM). Traditionally, the MFCS symposia encourage high-quality research in all branches of theoretical computer science. Ranging in scope from automata, f- mal languages, data structures, algorithms and computational geometry to c- plexitytheory,modelsofcomputation,andapplicationsincludingcomputational biology, cryptography, security and arti?cial intelligence, the conference o?ers a unique opportunity to researchers from diverse areas to meet and present their results to a general audience. The scienti?c program of this year’s MFCS took place in the lecture halls of the recently reconstructed building of the Faculty of Mathematics and P- sics in the historical center of Prague, with the famous Prague Castle and other celebratedhistoricalmonumentsinsight.Theviewfromthewindowswasach- lengingcompetitionforthespeakersinthe?ghtfortheattentionoftheaudience. But we did not fear the result: Due to the unusually tough competition for this year’s MFCS, the admitted presentations certainly attracted considerable in- rest. The conference program (and the proceedings) consisted of 60 contributed papers selected by the Program Committee from a total of 167 submissions.

---

Table of contents :
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 –