Mathematical Foundations of Computer Science 2005

Inhaltsverzeichnis

Invited Lectures.- Page Migration in Dynamic Networks.- Knot Theory, Jones Polynomial and Quantum Computing.- Interactive Algorithms 2005.- Some Computational Issues in Membrane Computing.- The Generalization of Dirac's Theorem for Hypergraphs.- On the Communication Complexity of Co-linearity Problems.- An Invitation to Play.- Papers.- The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.- On the Number of Random Digits Required in MonteCarlo Integration of Definable Functions.- Pure Nash Equilibria in Games with a Large Number of Actions.- On the Complexity of Depth-2 Circuits with Threshold Gates.- Isomorphic Implication.- Abstract Numeration Systems and Tilings.- Adversarial Queueing Model for Continuous Network Dynamics.- Coloring Sparse Random k-Colorable Graphs in Polynomial Expected Time.- Regular Sets of Higher-Order Pushdown Stacks.- Linearly Bounded Infinite Graphs.- Basic Properties for Sand Automata.- A Bridge Between the Asynchronous Message Passing Model and Local Computations in Graphs.- Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix.- New Resource Augmentation Analysis of the Total Stretch of SRPT and SJF in Multiprocessor Scheduling.- Approximating Polygonal Objects by Deformable Smooth Surfaces.- Basis of Solutions for a System of Linear Inequalities in Integers: Computation and Applications.- Asynchronous Deterministic Rendezvous in Graphs.- Zeta-Dimension.- Online Interval Coloring with Packing Constraints.- Separating the Notions of Self- and Autoreducibility.- Fully Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata.- Finding Exact and Maximum Occurrences of Protein Complexes in Protein-Protein Interaction Graphs.- Matrix and Graph Orders Derived from Locally Constrained Graph Homomorphisms.- Packing Weighted Rectangles into a Square.- Nondeterministic Graph Searching: From Pathwidth to Treewidth.- Goals in the Propositional Horn??? Language Are Monotone Boolean Circuits.- Autoreducibility, Mitoticity, and Immunity.- Canonical Disjoint NP-Pairs of Propositional Proof Systems.- Complexity of DNF and Isomorphism of Monotone Formulas.- The Expressive Power of Two-Variable Least Fixed-Point Logics.- Languages Representable by Vertex-Labeled Graphs.- On the Complexity of Mixed Discriminants and Related Problems.- Two Logical Hierarchies of Optimization Problems over the Real Numbers.- Algebras as Knowledge Structures.- Combining Self-reducibility and Partial Information Algorithms.- Complexity Bounds for Regular Games.- Basic Mereology with Equivalence Relations.- Online and Dynamic Recognition of Squarefree Strings.- Shrinking Restarting Automata.- Removing Bidirectionality from Nondeterministic Finite Automata.- Generating All Minimal Integral Solutions to Monotone ?,?-Systems of Linear, Transversal and Polymatroid Inequalities.- On the Parameterized Complexity of Exact Satisfiability Problems.- Approximating Reversal Distance for Strings with Bounded Number of Duplicates.- Random Databases and Threshold for Monotone Non-recursive Datalog.- An Asymptotically Optimal Linear-Time Algorithm for Locally Consistent Constraint Satisfaction Problems.- Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing.- Tight Approximability Results for the Maximum Solution Equation Problem over Z p .- The Complexity of Model Checking Higher Order Fixpoint Logic.- An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules.- Inverse Monoids: Decidability and Complexity of Algebraic Questions.- Dimension Is Compression.- Concurrent Automata vs. Asynchronous Systems.- Completeness and Degeneracy in Information Dynamics of Cellular Automata.- Strict Language Inequalities and Their Decision Problems.- Event Structures for the Collective Tokens Philosophy of Inhibitor Nets.- An Exact 2.9416 n Algorithm for the Three Domatic Number Problem.- D-Width: A More Natural Measure for Directed Tree Width.- On Beta-Shifts Having Arithmetical Languages.- A BDD-Representation for the Logic of Equality and Uninterpreted Functions.- On Small Hard Leaf Languages.- Explicit Inapproximability Bounds for the Shortest Superstring Problem.- Stratified Boolean Grammars.