Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29–September 2, 2005. Proceedings

Front Matter....Pages -
Page Migration in Dynamic Networks....Pages 1-14
Knot Theory, Jones Polynomial and Quantum Computing....Pages 15-25
Interactive Algorithms 2005....Pages 26-38
Some Computational Issues in Membrane Computing....Pages 39-51
The Generalization of Dirac’s Theorem for Hypergraphs....Pages 52-56
On the Communication Complexity of Co-linearity Problems....Pages 57-57
An Invitation to Play....Pages 58-70
The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem....Pages 71-82
On the Number of Random Digits Required in MonteCarlo Integration of Definable Functions....Pages 83-94
Pure Nash Equilibria in Games with a Large Number of Actions....Pages 95-106
On the Complexity of Depth-2 Circuits with Threshold Gates....Pages 107-118
Isomorphic Implication....Pages 119-130
Abstract Numeration Systems and Tilings....Pages 131-143
Adversarial Queueing Model for Continuous Network Dynamics....Pages 144-155
Coloring Sparse Random k -Colorable Graphs in Polynomial Expected Time....Pages 156-167
Regular Sets of Higher-Order Pushdown Stacks....Pages 168-179
Linearly Bounded Infinite Graphs....Pages 180-191
Basic Properties for Sand Automata....Pages 192-211
A Bridge Between the Asynchronous Message Passing Model and Local Computations in Graphs....Pages 212-223
Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix....Pages 224-235
New Resource Augmentation Analysis of the Total Stretch of SRPT and SJF in Multiprocessor Scheduling....Pages 236-247
Approximating Polygonal Objects by Deformable Smooth Surfaces....Pages 248-259
Basis of Solutions for a System of Linear Inequalities in Integers: Computation and Applications....Pages 260-270
Asynchronous Deterministic Rendezvous in Graphs....Pages 271-282
Zeta-Dimension....Pages 283-294
Online Interval Coloring with Packing Constraints....Pages 295-307
Separating the Notions of Self- and Autoreducibility....Pages 308-315
Fully Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata....Pages 316-327
Finding Exact and Maximum Occurrences of Protein Complexes in Protein-Protein Interaction Graphs....Pages 328-339
Matrix and Graph Orders Derived from Locally Constrained Graph Homomorphisms....Pages 340-351
Packing Weighted Rectangles into a Square....Pages 352-363
Nondeterministic Graph Searching: From Pathwidth to Treewidth....Pages 364-375
Goals in the Propositional Horn  ⊃  Language Are Monotone Boolean Circuits....Pages 376-386
Autoreducibility, Mitoticity, and Immunity....Pages 387-398
Canonical Disjoint NP-Pairs of Propositional Proof Systems....Pages 399-409
Complexity of DNF and Isomorphism of Monotone Formulas....Pages 410-421
The Expressive Power of Two-Variable Least Fixed-Point Logics....Pages 422-434
Languages Representable by Vertex-Labeled Graphs....Pages 435-446
On the Complexity of Mixed Discriminants and Related Problems....Pages 447-458
Two Logical Hierarchies of Optimization Problems over the Real Numbers....Pages 459-470
Algebras as Knowledge Structures....Pages 471-482
Combining Self-reducibility and Partial Information Algorithms....Pages 483-494
Complexity Bounds for Regular Games....Pages 495-506
Basic Mereology with Equivalence Relations....Pages 507-519
Online and Dynamic Recognition of Squarefree Strings....Pages 520-531
Shrinking Restarting Automata....Pages 532-543
Removing Bidirectionality from Nondeterministic Finite Automata....Pages 544-555
Generating All Minimal Integral Solutions to Monotone ∧,∨-Systems of Linear, Transversal and Polymatroid Inequalities....Pages 556-567
On the Parameterized Complexity of Exact Satisfiability Problems....Pages 568-579
Approximating Reversal Distance for Strings with Bounded Number of Duplicates....Pages 580-590
Random Databases and Threshold for Monotone Non-recursive Datalog....Pages 591-602
An Asymptotically Optimal Linear-Time Algorithm for Locally Consistent Constraint Satisfaction Problems....Pages 603-614
Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing....Pages 615-627
Tight Approximability Results for the Maximum Solution Equation Problem over Z p ....Pages 628-639
The Complexity of Model Checking Higher Order Fixpoint Logic....Pages 640-651
An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules....Pages 652-663
Inverse Monoids: Decidability and Complexity of Algebraic Questions....Pages 664-675
Dimension Is Compression....Pages 676-685
Concurrent Automata vs. Asynchronous Systems....Pages 686-698
Completeness and Degeneracy in Information Dynamics of Cellular Automata....Pages 699-707
Strict Language Inequalities and Their Decision Problems....Pages 708-719
Event Structures for the Collective Tokens Philosophy of Inhibitor Nets....Pages 720-732
An Exact 2.9416 n Algorithm for the Three Domatic Number Problem....Pages 733-744
D-Width: A More Natural Measure for Directed Tree Width....Pages 745-756
On Beta-Shifts Having Arithmetical Languages....Pages 757-768
A BDD-Representation for the Logic of Equality and Uninterpreted Functions....Pages 769-780
On Small Hard Leaf Languages....Pages 781-792
Explicit Inapproximability Bounds for the Shortest Superstring Problem....Pages 793-800
Stratified Boolean Grammars....Pages 801-812
Back Matter....Pages -