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

Marcin Bienkowski, Friedhelm Meyer auf der Heide (auth.), Joanna Jȩdrzejowicz, Andrzej Szepietowski (eds.)3540287027, 9783540287025

This book constitutes the refereed proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, MFCS 2005, held in Gdansk, Poland in August/September 2005.

The 62 revised full papers presented together with full papers or abstracts of 7 invited talks were carefully reviewed and selected from 137 submissions. All current aspects in theoretical computer science are addressed, ranging from quantum computing, approximation, automata, circuits, scheduling, games, languages, discrete mathematics, combinatorial optimization, graph theory, networking, algorithms, and complexity to programming theory, formal methods, and mathematical logic.

---

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