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

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 -