Mathematical Foundations of Computer Science 2003

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Distributed Quantum Computing
3. Altmetric Badge
   Chapter 2 Mathematical Foundations of Computer Science 2003
4. Altmetric Badge
   Chapter 3 Process Algebraic Frameworks for the Specification and Analysis of Cryptographic Protocols
5. Altmetric Badge
   Chapter 4 Semantic and Syntactic Approaches to Simulation Relations
6. Altmetric Badge
   Chapter 5 On the Computational Complexity of Conservative Computing
7. Altmetric Badge
   Chapter 6 Constructing Infinite Graphs with a Decidable MSO-Theory
8. Altmetric Badge
   Chapter 7 Towards a Theory of Randomized Search Heuristics
9. Altmetric Badge
   Chapter 8 Adversarial Models for Priority-Based Networks
10. Altmetric Badge
    Chapter 9 On Optimal Merging Networks
11. Altmetric Badge
    Chapter 10 Problems which Cannot Be Reduced to Any Proper Subproblems
12. Altmetric Badge
    Chapter 11 ACID -Unification Is NEXPTIME-Decidable
13. Altmetric Badge
    Chapter 12 Completeness in Differential Approximation Classes
14. Altmetric Badge
    Chapter 13 On the Length of the Minimum Solution of Word Equations in One Variable
15. Altmetric Badge
    Chapter 14 Smoothed Analysis of Three Combinatorial Problems
16. Altmetric Badge
    Chapter 15 Inferring Strings from Graphs and Arrays
17. Altmetric Badge
    Chapter 16 Faster Algorithms for k -Medians in Trees
18. Altmetric Badge
    Chapter 17 Periodicity and Transitivity for Cellular Automata in Besicovitch Topologies
19. Altmetric Badge
    Chapter 18 Starting with Nondeterminism: The Systematic Derivation of Linear-Time Graph Layout Algorithms
20. Altmetric Badge
    Chapter 19 Error-Bounded Probabilistic Computations between MA and AM
21. Altmetric Badge
    Chapter 20 A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves
22. Altmetric Badge
    Chapter 21 Symbolic Analysis of Crypto-Protocols Based on Modular Exponentiation
23. Altmetric Badge
    Chapter 22 Denotational Testing Semantics in Coinductive Form
24. Altmetric Badge
    Chapter 23 Lower Bounds for General Graph–Driven Read–Once Parity Branching Programs
25. Altmetric Badge
    Chapter 24 The Minimal Graph Model of Lambda Calculus
26. Altmetric Badge
    Chapter 25 Unambiguous Automata on Bi-infinite Words
27. Altmetric Badge
    Chapter 26 Relating Hierarchy of Temporal Properties to Model Checking
28. Altmetric Badge
    Chapter 27 Arithmetic Constant-Depth Circuit Complexity Classes
29. Altmetric Badge
    Chapter 28 Inverse NP Problems
30. Altmetric Badge
    Chapter 29 A Linear-Time Algorithm for 7-Coloring 1-Planar Graphs
31. Altmetric Badge
    Chapter 30 Generalized Satisfiability with Limited Occurrences per Variable: A Study through Delta-Matroid Parity
32. Altmetric Badge
    Chapter 31 Randomized Algorithms for Determining the Majority on Graphs
33. Altmetric Badge
    Chapter 32 Using Transitive–Closure Logic for Deciding Linear Properties of Monoids
34. Altmetric Badge
    Chapter 33 Linear-Time Computation of Local Periods
35. Altmetric Badge
    Chapter 34 Two Dimensional Packing: The Power of Rotation
36. Altmetric Badge
    Chapter 35 Approximation Schemes for the Min-Max Starting Time Problem
37. Altmetric Badge
    Chapter 36 Quantum Testers for Hidden Group Properties
38. Altmetric Badge
    Chapter 37 Local LTL with Past Constants Is Expressively Complete for Mazurkiewicz Traces
39. Altmetric Badge
    Chapter 38 LTL with Past and Two-Way Very-Weak Alternating Automata
40. Altmetric Badge
    Chapter 39 Match-Bounded String Rewriting Systems
41. Altmetric Badge
    Chapter 40 Probabilistic and Nondeterministic Unary Automata
42. Altmetric Badge
    Chapter 41 On Matroid Properties Definable in the MSO Logic
43. Altmetric Badge
    Chapter 42 Characterizations of Catalytic Membrane Computing Systems
44. Altmetric Badge
    Chapter 43 Augmenting Local Edge-Connectivity between Vertices and Vertex Subsets in Undirected Graphs
45. Altmetric Badge
    Chapter 44 Scheduling and Traffic Allocation for Tasks with Bounded Splittability
46. Altmetric Badge
    Chapter 45 Computing Average Value in Ad Hoc Networks
47. Altmetric Badge
    Chapter 46 A Polynomial-Time Algorithm for Deciding True Concurrency Equivalences of Basic Parallel Processes
48. Altmetric Badge
    Chapter 47 Solving the Sabotage Game Is PSPACE-Hard
49. Altmetric Badge
    Chapter 48 The Approximate Well-Founded Semantics for Logic Programs with Uncertainty
50. Altmetric Badge
    Chapter 49 Which Is the Worst-Case Nash Equilibrium?
51. Altmetric Badge
    Chapter 50 A Unique Decomposition Theorem for Ordered Monoids with Applications in Process Theory
52. Altmetric Badge
    Chapter 51 Generic Algorithms for the Generation of Combinatorial Objects
53. Altmetric Badge
    Chapter 52 On the Complexity of Some Problems in Interval Arithmetic
54. Altmetric Badge
    Chapter 53 An Abduction-Based Method for Index Relaxation in Taxonomy-Based Sources
55. Altmetric Badge
    Chapter 54 On Selection Functions that Do Not Preserve Normality
56. Altmetric Badge
    Chapter 55 On Converting CNF to DNF
57. Altmetric Badge
    Chapter 56 A Basis of Tiling Motifs for Generating Repeated Patterns and Its Complexity for Higher Quorum
58. Altmetric Badge
    Chapter 57 On the Complexity of Some Equivalence Problems for Propositional Calculi
59. Altmetric Badge
    Chapter 58 Quantified Mu-Calculus for Control Synthesis
60. Altmetric Badge
    Chapter 59 On Probabilistic Quantified Satisfiability Games
61. Altmetric Badge
    Chapter 60 A Completeness Property of Wilke’s Tree Algebras
62. Altmetric Badge
    Chapter 61 Symbolic Topological Sorting with OBDDs
63. Altmetric Badge
    Chapter 62 Ershov’s Hierarchy of Real Numbers