Mathematical Foundations of Computer Science 2003: 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003. Proceedings

Harry Buhrman, Hein Röhrig (auth.), Branislav Rovan, Peter Vojtáš (eds.)3540406719, 9783540406716

This book constitutes the refereed proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science, MFCS 2003, held in Bratislava, Slovakia in August 2003.

The 55 revised full papers presented together with 7 invited papers were carefully reviewed and selected from 137 submissions. All current aspects in theoretical computer science are addressed, ranging from discrete mathematics, combinatorial optimization, graph theory, networking, algorithms, and complexity to programming theory, formal methods, and mathematical logic.

---

Table of contents :
Front Matter….Pages –
Distributed Quantum Computing….Pages 1-20
Selfish Routing in Non-cooperative Networks: A Survey….Pages 21-45
Process Algebraic Frameworks for the Specification and Analysis of Cryptographic Protocols….Pages 46-67
Semantic and Syntactic Approaches to Simulation Relations….Pages 68-91
On the Computational Complexity of Conservative Computing….Pages 92-112
Constructing Infinite Graphs with a Decidable MSO-Theory….Pages 113-124
Towards a Theory of Randomized Search Heuristics….Pages 125-141
Adversarial Models for Priority-Based Networks….Pages 142-151
On Optimal Merging Networks….Pages 152-161
Problems which Cannot Be Reduced to Any Proper Subproblems….Pages 162-168
ACID -Unification Is NEXPTIME-Decidable….Pages 169-178
Completeness in Differential Approximation Classes….Pages 179-188
On the Length of the Minimum Solution of Word Equations in One Variable….Pages 189-197
Smoothed Analysis of Three Combinatorial Problems….Pages 198-207
Inferring Strings from Graphs and Arrays….Pages 208-217
Faster Algorithms for k -Medians in Trees….Pages 218-227
Periodicity and Transitivity for Cellular Automata in Besicovitch Topologies….Pages 228-238
Starting with Nondeterminism: The Systematic Derivation of Linear-Time Graph Layout Algorithms….Pages 239-248
Error-Bounded Probabilistic Computations between MA and AM….Pages 249-258
A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves….Pages 259-268
Symbolic Analysis of Crypto-Protocols Based on Modular Exponentiation….Pages 269-278
Denotational Testing Semantics in Coinductive Form….Pages 279-289
Lower Bounds for General Graph–Driven Read–Once Parity Branching Programs….Pages 290-299
The Minimal Graph Model of Lambda Calculus….Pages 300-307
Unambiguous Automata on Bi-infinite Words….Pages 308-317
Relating Hierarchy of Temporal Properties to Model Checking….Pages 318-327
Arithmetic Constant-Depth Circuit Complexity Classes….Pages 328-337
Inverse NP Problems….Pages 338-347
A Linear-Time Algorithm for 7-Coloring 1-Planar Graphs….Pages 348-357
Generalized Satisfiability with Limited Occurrences per Variable: A Study through Delta-Matroid Parity….Pages 358-367
Randomized Algorithms for Determining the Majority on Graphs….Pages 368-377
Using Transitive–Closure Logic for Deciding Linear Properties of Monoids….Pages 378-387
Linear-Time Computation of Local Periods….Pages 388-397
Two Dimensional Packing: The Power of Rotation….Pages 398-407
Approximation Schemes for the Min-Max Starting Time Problem….Pages 408-418
Quantum Testers for Hidden Group Properties….Pages 419-428
Local LTL with Past Constants Is Expressively Complete for Mazurkiewicz Traces….Pages 429-438
LTL with Past and Two-Way Very-Weak Alternating Automata….Pages 439-448
Match-Bounded String Rewriting Systems….Pages 449-459
Probabilistic and Nondeterministic Unary Automata….Pages 460-469
On Matroid Properties Definable in the MSO Logic….Pages 470-479
Characterizations of Catalytic Membrane Computing Systems….Pages 480-489
Augmenting Local Edge-Connectivity between Vertices and Vertex Subsets in Undirected Graphs….Pages 490-499
Scheduling and Traffic Allocation for Tasks with Bounded Splittability….Pages 500-510
Computing Average Value in Ad Hoc Networks….Pages 511-520
A Polynomial-Time Algorithm for Deciding True Concurrency Equivalences of Basic Parallel Processes….Pages 521-530
Solving the Sabotage Game Is PSPACE-Hard….Pages 531-540
The Approximate Well-Founded Semantics for Logic Programs with Uncertainty….Pages 541-550
Which Is the Worst-Case Nash Equilibrium?….Pages 551-561
A Unique Decomposition Theorem for Ordered Monoids with Applications in Process Theory….Pages 562-571
Generic Algorithms for the Generation of Combinatorial Objects….Pages 572-581
On the Complexity of Some Problems in Interval Arithmetic….Pages 582-591
An Abduction-Based Method for Index Relaxation in Taxonomy-Based Sources….Pages 592-601
On Selection Functions that Do Not Preserve Normality….Pages 602-611
On Converting CNF to DNF….Pages 612-621
A Basis of Tiling Motifs for Generating Repeated Patterns and Its Complexity for Higher Quorum….Pages 622-631
On the Complexity of Some Equivalence Problems for Propositional Calculi….Pages 632-641
Quantified Mu-Calculus for Control Synthesis….Pages 642-651
On Probabilistic Quantified Satisfiability Games….Pages 652-661
A Completeness Property of Wilke’s Tree Algebras….Pages 662-670
Symbolic Topological Sorting with OBDDs….Pages 671-680
Ershov’s Hierarchy of Real Numbers….Pages 681-690
Back Matter….Pages –