دانلود کتاب Mathematical Foundations of Computer Science 2004: 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings

فهرست مطالب :

Table of Contents
Invited Lectures
A Case Study of Genome Evolution: From Continuous to Discrete Time Model
Multicoloring: Problems and Techniques
Some Recent Progress in Algorithmic Randomness
Ubiquitous Parameterization — Invitation to Fixed-Parameter Algorithms
PRAM-On-Chip: A Quest for Not-So-Obvious Non-obviousness
Theory and Applied Computing: Observations and Anecdotes
Boxed Ambients with Communication Interfaces
Algebraic Recognizability of Languages
Geometric Optimization and Unique Sink Orientations of Cubes
Congestion Games and Coordination Mechanisms
Graph Algorithms
Equitable Colorings of Bounded Treewidth Graphs
The Bidimensional Theory of Bounded-Genus Graphs
Parallel Knock-Out Schemes in Networks
Online Algorithms for Disk Graphs
Approximations
Protein Folding in the HP Model on Grid Lattices with Diagonals
Optimization, Games, and Quantified Constraint Satisfaction
Approximating Boolean Functions by OBDDs
On Approximation Hardness of the Minimum 2SAT-DELETION Problem
Graphs and Complexity
Group Coloring and List Group Coloring Are Π[sup(p)][sub(2)]-Complete
Complexity Results in Graph Reconstruction
Generating Paths and Cuts in Multi-pole (Di)graphs
Packing Directed Cycles Efficiently
Circuits
The Complexity of Membership Problems for Circuits over Sets of Integers
Some Meet-in-the-Middle Circuit Lower Bounds
The Enumerability of P Collapses P to NC
On NC[sup(1)] Boolean Circuit Composition of Non-interactive Perfect Zero-Knowledge
General Complexity
All Superlinear Inverse Schemes Are coNP-Hard
The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups
Generation Problems
One Query Reducibilities Between Partial Information Classes
Automata
A New Dimension Sensitive Property for Cellular Automata
Captive Cellular Automata
Simulating 3D Cellular Automata with 2D Cellular Automata
Graph Exploration by a Finite Automaton
Parametrized and Kolmogorov Complexity
On Polynomially 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
Author Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
R
S
T
V
W
X
Y
Z