Automata, Languages and Programming

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Algorithms, Games, and the Internet
3. Altmetric Badge
   Chapter 2 Automata, Circuits, and Hybrids: Facets of Continuous Time
4. Altmetric Badge
   Chapter 3 Languages, Rewriting Systems, and Verification of Infinite-State Systems
5. Altmetric Badge
   Chapter 4 Integrating Semantics for Object—Oriented System Models
6. Altmetric Badge
   Chapter 5 Modelling with Partial Orders — Why and Why Not?
7. Altmetric Badge
   Chapter 6 Theoretical Aspects of Evolutionary Algorithms
8. Altmetric Badge
   Chapter 7 Improvements of the Alder—Strassen Bound: Algebras with Nonzero Radical
9. Altmetric Badge
   Chapter 8 On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities
10. Altmetric Badge
    Chapter 9 Division Is In Uniform TC0
11. Altmetric Badge
    Chapter 10 A Framework for Index Bulk Loading and Dynamization
12. Altmetric Badge
    Chapter 11 A Characterization of Temporal Locality and Its Portability across Memory Hierarchies
13. Altmetric Badge
    Chapter 12 The Complexity of Constructing Evolutionary Trees Using Experiments
14. Altmetric Badge
    Chapter 13 Hidden Pattern Statistics
15. Altmetric Badge
    Chapter 14 Combinatorics and Algorithms on Low-Discrepancy Roundings of a Real Sequence
16. Altmetric Badge
    Chapter 15 All-Pairs Shortest Paths Computation in the BSP Model
17. Altmetric Badge
    Chapter 16 Approximating the Minimum Spanning Tree Weight in Sublinear Time
18. Altmetric Badge
    Chapter 17 Approximation Hardness of TSP with Bounded Metrics
19. Altmetric Badge
    Chapter 18 The RPR 2 Rounding Technique for Semidefinite Programs
20. Altmetric Badge
    Chapter 19 Approximation Algorithms for Partial Covering Problems
21. Altmetric Badge
    Chapter 20 On the Online Bin Packing Problem
22. Altmetric Badge
    Chapter 21 Quick k-Median, k-Center, and Facility Location for Sparse Graphs
23. Altmetric Badge
    Chapter 22 Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems
24. Altmetric Badge
    Chapter 23 Subexponential Parameterized Algorithms Collapse the W-Hierarchy
25. Altmetric Badge
    Chapter 24 Improved Lower Bounds on the Randomized Complexity of Graph Properties
26. Altmetric Badge
    Chapter 25 New Imperfect Random Source with Applications to Coin-Flipping
27. Altmetric Badge
    Chapter 26 Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently
28. Altmetric Badge
    Chapter 27 Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations
29. Altmetric Badge
    Chapter 28 On Interactive Proofs with a Laconic Prover
30. Altmetric Badge
    Chapter 29 Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness
31. Altmetric Badge
    Chapter 30 Lower Bounds in the Quantum Cell Probe Model
32. Altmetric Badge
    Chapter 31 Axiomatizations for Probabilistic Bisimulation
33. Altmetric Badge
    Chapter 32 Noninterference for Concurrent Programs
34. Altmetric Badge
    Chapter 33 Distributed Controller Synthesis for Local Specifications
35. Altmetric Badge
    Chapter 34 A Distributed Abstract Machine for Safe Ambients
36. Altmetric Badge
    Chapter 35 Towards Quantitative Verification of Probabilistic Transition Systems
37. Altmetric Badge
    Chapter 36 Efficient Generation of Plane Triangulations without Repetitions
38. Altmetric Badge
    Chapter 37 The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations
39. Altmetric Badge
    Chapter 38 Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher
40. Altmetric Badge
    Chapter 39 A New Method for Balancing Binary Search Trees
41. Altmetric Badge
    Chapter 40 Permutation Editing and Matching via Embeddings
42. Altmetric Badge
    Chapter 41 Testing Hypergraph Coloring
43. Altmetric Badge
    Chapter 42 Total Colorings of Degenerated Graphs
44. Altmetric Badge
    Chapter 43 Decidable Properties of Graphs of All-Optical Networks
45. Altmetric Badge
    Chapter 44 Majority Consensus and the Local Majority Rule
46. Altmetric Badge
    Chapter 45 Solvability of Equations in Free Partially Commutative Groups Is decidable
47. Altmetric Badge
    Chapter 46 Rational Transformations of Formal Power Series
48. Altmetric Badge
    Chapter 47 Combinatorics of Three-Interval Exchanges
49. Altmetric Badge
    Chapter 48 Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages
50. Altmetric Badge
    Chapter 49 The Star Problem in Trace Monoids: Reductions Beyond C4
51. Altmetric Badge
    Chapter 50 The Trace Coding Problem Is Undecidable
52. Altmetric Badge
    Chapter 51 Combinatorics of Periods in Strings
53. Altmetric Badge
    Chapter 52 Minimal Tail-Biting Trellises for Certain Cyclic Block Codes Are Easy to Construct
54. Altmetric Badge
    Chapter 53 Effective Lossy Queue Languages
55. Altmetric Badge
    Chapter 54 Model Checking of Unrestricted Hierarchical State Machines
56. Altmetric Badge
    Chapter 55 Symbolic Trace Analysis of Cryptographic Protocols
57. Altmetric Badge
    Chapter 56 Tree Automata with One Memory, Set Constraints, and Ping-Pong Protocols
58. Altmetric Badge
    Chapter 57 Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata
59. Altmetric Badge
    Chapter 58 Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width
60. Altmetric Badge
    Chapter 59 From Finite State Communication Protocols to High-Level Message Sequence Charts
61. Altmetric Badge
    Chapter 60 Fractional Path Coloring with Applications to WDM Networks
62. Altmetric Badge
    Chapter 61 Performance Aspects of Distributed Caches Using TTL-Based Consistency
63. Altmetric Badge
    Chapter 62 Routing in Trees
64. Altmetric Badge
    Chapter 63 Online Packet Routing on Linear Arrays and Rings
65. Altmetric Badge
    Chapter 64 Faster Gossiping on Butterflies
66. Altmetric Badge
    Chapter 65 Realizability and Verification of MSC Graphs
67. Altmetric Badge
    Chapter 66 Reasoning about Sequential and Branching Behaviours of Message Sequence Graphs
68. Altmetric Badge
    Chapter 67 A Set-Theoretic Framework for Assume-Guarantee Reasoning
69. Altmetric Badge
    Chapter 68 Foundations for Circular Compositional Reasoning
70. Altmetric Badge
    Chapter 69 A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines
71. Altmetric Badge
    Chapter 70 The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts
72. Altmetric Badge
    Chapter 71 On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates
73. Altmetric Badge
    Chapter 72 On the Approximability of Average Completion Time Scheduling under Precedence Constraints
74. Altmetric Badge
    Chapter 73 Optimistic Asynchronous Multi-party Contract Signing with Reduced Number of Rounds
75. Altmetric Badge
    Chapter 74 Information-Theoretic Private Information Retrieval: A Unified Construction
76. Altmetric Badge
    Chapter 75 Secure Multiparty Computation of Approximations
77. Altmetric Badge
    Chapter 76 Secure Games with Polynomial Expressions
78. Altmetric Badge
    Chapter 77 On the Completeness of Arbitrary Selection Strategies for Paramodulation
79. Altmetric Badge
    Chapter 78 An Axiomatic Approach to Metareasoning on Nominal Algebras in HOAS
80. Altmetric Badge
    Chapter 79 Knuth-Bendix Constraint Solving Is NP-Complete
81. Altmetric Badge
    Chapter 80 Amalgamation in CASL via Enriched Signatures
82. Altmetric Badge
    Chapter 81 Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution
83. Altmetric Badge
    Chapter 82 Time and Space Bounds for Reversible Simulation
84. Altmetric Badge
    Chapter 83 Finite-State Dimension
85. Altmetric Badge
    Chapter 84 The Complexity of Computing the Size of an Interval
86. Altmetric Badge
    Chapter 85 Communication Gap for Finite Memory Devices
87. Altmetric Badge
    Chapter 86 Separating Quantum and Classical Learning