Mathematical Foundations of Computer Science 2004

Time Bounded Symmetry of Information.- Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets.- A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs.- Polynomial Time Approximation Schemes and Parameterized Complexity.- Semantics.- Epistemic Foundation of the Well-Founded Semantics over Bilattices.- Structural Model Checking for Communicating Hierarchical Machines.- Compositional Verification: Decidability Issues Using Graph Substitutions.- Event Structures for Resolvable Conflict.- Scheduling.- Optimal Preemptive Scheduling for General Target Functions.- The Price of Anarchy for Polynomial Social Cost.- Agent-Based Information Handling in Large Networks.- Approximating Earliest Arrival Flows with Flow-Dependent Transit Times.- Algebraic Theory of Languages.- A Hierarchy of Irreducible Sofic Shifts.- Membership and Reachability Problems for Row-Monomial Transformations.- On Pseudovarieties of Semiring Homomorphisms.- An Algebraic Generalization of ?-Regular Languages.- Games.- A Protocol for Serializing Unique Strategies.- A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games.- When Can You Play Positionally?.- Languages.- The Dual of Concatenation.- Computational Aspects of Disjunctive Sequences.- Decidability of Trajectory-Based Equations.- Geometry.- Efficient View Point Selection for Silhouettes of Convex Polyhedra.- Angles and Lengths in Reconfigurations of Polygons and Polyhedra.- Improved Bounds and Schemes for the Declustering Problem.- Crossing Number Is Hard for Cubic Graphs.- Languages and Complexity.- A Reducibility for the Dot-Depth Hierarchy.- Sublogarithmic Ambiguity.- An Elementary Proof for the Non-parametrizability of the Equation xyz=zvx.- A Generalization of Repetition Threshold.- Quantum Computing.- An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation.- Universal Test for Quantum One-Way Permutations.- A Common Algebraic Description for Probabilistic and Quantum Computations.- XML.- Extraction and Implication of Path Constraints.- Schema Evolution for XML: A Consistency-Preserving Approach.- Complexity of Decision Problems for Simple Regular Expressions.