Mathematical Foundations of Computer Science 2000

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Region Analysis and a π-Calculus with Groups
3. Altmetric Badge
   Chapter 2 Abstract Data Types in Computer Algebra
4. Altmetric Badge
   Chapter 3 What Do We Learn from Experimental Algorithmics?
5. Altmetric Badge
   Chapter 4 And/Or Hierarchies and Round Abstraction
6. Altmetric Badge
   Chapter 5 Computational Politics: Electoral Systems
7. Altmetric Badge
   Chapter 6 0–1 Laws for Fragments of Existential Second-Order Logic: A Survey
8. Altmetric Badge
   Chapter 7 On Algorithms and Interaction
9. Altmetric Badge
   Chapter 8 On the Use of Duality and Geometry in Layouts for ATM Networks
10. Altmetric Badge
    Chapter 9 On the Lower Bounds for One-Way Quantum Automata
11. Altmetric Badge
    Chapter 10 Axiomatizing Fully Complete Models for ML Polymorphic Types
12. Altmetric Badge
    Chapter 11 Measure Theoretic Completeness Notions for the Exponential Time Classes
13. Altmetric Badge
    Chapter 12 Edge-Bisection of Chordal Rings
14. Altmetric Badge
    Chapter 13 Equation Satisfiability and Program Satisfiability for Finite Monoids
15. Altmetric Badge
    Chapter 14 XML Grammars
16. Altmetric Badge
    Chapter 15 Simplifying Flow Networks
17. Altmetric Badge
    Chapter 16 Balanced k-Colorings
18. Altmetric Badge
    Chapter 17 A Compositional Model for Confluent Dynamic Data-Flow Networks
19. Altmetric Badge
    Chapter 18 Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
20. Altmetric Badge
    Chapter 19 Expressiveness of Updatable Timed Automata
21. Altmetric Badge
    Chapter 20 Iterative Arrays with Small Time Bounds
22. Altmetric Badge
    Chapter 21 Embedding Fibonacci Cubes into Hypercubes with Ω(2cn) Faulty Nodes
23. Altmetric Badge
    Chapter 22 Periodic-Like Words
24. Altmetric Badge
    Chapter 23 The Monadic Theory of Morphic Infinite Words and Generalizations
25. Altmetric Badge
    Chapter 24 Optical Routing of Uniform Instances in Tori
26. Altmetric Badge
    Chapter 25 Factorizing Codes and Schützenberger Conjectures
27. Altmetric Badge
    Chapter 26 Compositional Characterizations of λ-Terms Using Intersection Types
28. Altmetric Badge
    Chapter 27 Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks
29. Altmetric Badge
    Chapter 28 Subtractive Reductions and Complete Problems for Counting Complexity Classes
30. Altmetric Badge
    Chapter 29 On the Autoreducibility of Random Sequences
31. Altmetric Badge
    Chapter 30 Iteration Theories of Boolean Functions
32. Altmetric Badge
    Chapter 31 An Algorithm Constructing the Semilinear Post for 2-Dim Reset/Transfer VASS
33. Altmetric Badge
    Chapter 32 NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs
34. Altmetric Badge
    Chapter 33 Explicit Fusions
35. Altmetric Badge
    Chapter 34 State Space Reduction Using Partial τ-Confluence
36. Altmetric Badge
    Chapter 35 Reducing the Number of Solutions of NP Functions
37. Altmetric Badge
    Chapter 36 Regular Collections of Message Sequence Charts
38. Altmetric Badge
    Chapter 37 Alternating and Empty Alternating Auxiliary Stack Automata
39. Altmetric Badge
    Chapter 38 Counter Machines: Decidable Properties and Applications to Verification Problems
40. Altmetric Badge
    Chapter 39 A Family of NFA’s Which Need 2n — α Deterministic States
41. Altmetric Badge
    Chapter 40 Preemptive Scheduling on Dedicated Processors: Applications of Fractional Graph Coloring
42. Altmetric Badge
    Chapter 41 Matching Modulo Associativity and Idempotency Is NP—Complete
43. Altmetric Badge
    Chapter 42 On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems
44. Altmetric Badge
    Chapter 43 Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and Their Generalization
45. Altmetric Badge
    Chapter 44 Formal Series over Algebras
46. Altmetric Badge
    Chapter 45 μ-Calculus Synthesis
47. Altmetric Badge
    Chapter 46 The Infinite Versions of LogSpace ≠ P Are Consistent with the Axioms of Set Theory
48. Altmetric Badge
    Chapter 47 Timed Automata with Monotonic Activities
49. Altmetric Badge
    Chapter 48 On a Generalization of Bi-Complement Reducible Graphs
50. Altmetric Badge
    Chapter 49 Automatic Graphs and Graph D0L-Systems
51. Altmetric Badge
    Chapter 50 Bilinear Functions and Trees over the (max, +) Semiring
52. Altmetric Badge
    Chapter 51 Derivability in Locally Quantified Modal Logics via Translation in Set Theory
53. Altmetric Badge
    Chapter 52 π-Calculus, Structured Coalgebras, and Minimal HD-Automata
54. Altmetric Badge
    Chapter 53 Informative Labeling Schemes for Graphs
55. Altmetric Badge
    Chapter 54 Separation Results for Rebound Automata
56. Altmetric Badge
    Chapter 55 Unary Pushdown Automata and Auxiliary Space Lower Bounds
57. Altmetric Badge
    Chapter 56 Binary Decision Diagrams by Shared Rewriting
58. Altmetric Badge
    Chapter 57 Verifying Single and Multi-mutator Garbage Collectors with Owicki-Gries in Isabelle/HOL
59. Altmetric Badge
    Chapter 58 Why so Many Temporal Logics Climb up the Trees?
60. Altmetric Badge
    Chapter 59 Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems
61. Altmetric Badge
    Chapter 60 A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism
62. Altmetric Badge
    Chapter 61 On Diving in Trees Thomas Schwentick
63. Altmetric Badge
    Chapter 62 Abstract Syntax and Variable Binding for Linear Binders
64. Altmetric Badge
    Chapter 63 Regularity of Congruential Graphs
65. Altmetric Badge
    Chapter 64 Sublinear Ambiguity
66. Altmetric Badge
    Chapter 65 An Automata-Based Recognition Algorithm for Semi-extended Regular Expressions