Automata, Languages and Programming

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Self-Adjusting Computation
3. Altmetric Badge
   Chapter 2 The Past, Present, and Future of Web Search Engines
4. Altmetric Badge
   Chapter 3 What Do Program Logics and Type Systems Have in Common?
5. Altmetric Badge
   Chapter 4 Feasible Proofs and Computations: Partnership and Fusion
6. Altmetric Badge
   Chapter 5 Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input
7. Altmetric Badge
   Chapter 6 Testing, Optimizaton, and Games
8. Altmetric Badge
   Chapter 7 Deciding Knowledge in Security Protocols Under Equational Theories
9. Altmetric Badge
   Chapter 8 Representing Nested Inductive Types Using W-Types
10. Altmetric Badge
    Chapter 9 Algorithms for Multi-product Pricing
11. Altmetric Badge
    Chapter 10 Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas
12. Altmetric Badge
    Chapter 11 Linear and Branching Metrics for Quantitative Transition Systems
13. Altmetric Badge
    Chapter 12 Learning a Hidden Subgraph
14. Altmetric Badge
    Chapter 13 Optimal Reachability for Weighted Timed Games
15. Altmetric Badge
    Chapter 14 Wavelength Assignment in Optical Networks with Fixed Fiber Capacity
16. Altmetric Badge
    Chapter 15 External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphs
17. Altmetric Badge
    Chapter 16 A λ-Calculus for Resource Separation
18. Altmetric Badge
    Chapter 17 The Power of Verification for One-Parameter Agents
19. Altmetric Badge
    Chapter 18 Group Spreading: A Protocol for Provably Secure Distributed Name Service
20. Altmetric Badge
    Chapter 19 Further Improvements in Competitive Guarantees for QoS Buffering
21. Altmetric Badge
    Chapter 20 Competition-Induced Preferential Attachment
22. Altmetric Badge
    Chapter 21 Approximating Longest Directed Paths and Cycles
23. Altmetric Badge
    Chapter 22 Definitions and Bounds for Self-Healing Key Distribution Schemes
24. Altmetric Badge
    Chapter 23 Tree-Walking Automata Cannot Be Determinized
25. Altmetric Badge
    Chapter 24 Projecting Games on Hypercoherences
26. Altmetric Badge
    Chapter 25 An Analog Characterization of Elementarily Computable Functions over the Real Numbers
27. Altmetric Badge
    Chapter 26 Model Checking with Multi-valued Logics
28. Altmetric Badge
    Chapter 27 The Complexity of Partition Functions
29. Altmetric Badge
    Chapter 28 Comparing Recursion, Replication, and Iteration in Process Calculi
30. Altmetric Badge
    Chapter 29 Dynamic Price Sequence and Incentive Compatibility
31. Altmetric Badge
    Chapter 30 The Complexity of Equivariant Unification
32. Altmetric Badge
    Chapter 31 Coordination Mechanisms
33. Altmetric Badge
    Chapter 32 Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help
34. Altmetric Badge
    Chapter 33 Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities
35. Altmetric Badge
    Chapter 34 Coloring Semirandom Graphs Optimally
36. Altmetric Badge
    Chapter 35 Sublinear-Time Approximation for Clustering Via Random Sampling
37. Altmetric Badge
    Chapter 36 Solving Two-Variable Word Equations
38. Altmetric Badge
    Chapter 37 Automata, Languages and Programming
39. Altmetric Badge
    Chapter 38 A PTAS for Embedding Hypergraph in a Cycle
40. Altmetric Badge
    Chapter 39 Towards an Algebraic Theory of Typed Mobile Processes
41. Altmetric Badge
    Chapter 40 Ecological Turing Machines
42. Altmetric Badge
    Chapter 41 Locally Consistent Constraint Satisfaction Problems
43. Altmetric Badge
    Chapter 42 Quantum Query Complexity of Some Graph Problems
44. Altmetric Badge
    Chapter 43 A Domain Theoretic Account of Picard’s Theorem
45. Altmetric Badge
    Chapter 44 Interactive Observability in Ludics
46. Altmetric Badge
    Chapter 45 Easily Refutable Subformulas of Large Random 3CNF Formulas
47. Altmetric Badge
    Chapter 46 On Graph Problems in a Semi-streaming Model
48. Altmetric Badge
    Chapter 47 Linear Tolls Suffice: New Bounds and Algorithms for Tolls in Single Source Networks
49. Altmetric Badge
    Chapter 48 Bounded Fixed-Parameter Tractability and log2 n Nondeterministic Bits
50. Altmetric Badge
    Chapter 49 Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In
51. Altmetric Badge
    Chapter 50 Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up
52. Altmetric Badge
    Chapter 51 Selfish Unsplittable Flows
53. Altmetric Badge
    Chapter 52 A General Technique for Managing Strings in Comparison-Driven Data Structures
54. Altmetric Badge
    Chapter 53 Greedy Regular Expression Matching
55. Altmetric Badge
    Chapter 54 A $2^{O(n^{1-{1\over d}}\log n)}$ Time Algorithm for d-Dimensional Protein Folding in the HP-Model
56. Altmetric Badge
    Chapter 55 Automata, Languages and Programming
57. Altmetric Badge
    Chapter 56 Improved Results for Data Migration and Open Shop Scheduling
58. Altmetric Badge
    Chapter 57 Deterministic M2M Multicast in Radio Networks
59. Altmetric Badge
    Chapter 58 Syntactic Control of Concurrency
60. Altmetric Badge
    Chapter 59 Linear-Time List Decoding in Error-Free Settings
61. Altmetric Badge
    Chapter 60 A Categorical Model for the Geometry of Interaction
62. Altmetric Badge
    Chapter 61 Testing Monotonicity over Graph Products
63. Altmetric Badge
    Chapter 62 The Minimum-Entropy Set Cover Problem
64. Altmetric Badge
    Chapter 63 Communication Versus Computation
65. Altmetric Badge
    Chapter 64 Optimal Website Design with the Constrained Subtree Selection Problem
66. Altmetric Badge
    Chapter 65 Simple Permutations Mix Well
67. Altmetric Badge
    Chapter 66 Closest Pair Problems in Very High Dimensions
68. Altmetric Badge
    Chapter 67 Universality in Quantum Computation
69. Altmetric Badge
    Chapter 68 Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design
70. Altmetric Badge
    Chapter 69 Fairness to All While Downsizing
71. Altmetric Badge
    Chapter 70 A Generalisation of Pre-logical Predicates to Simply Typed Formal Systems
72. Altmetric Badge
    Chapter 71 A Faster Algorithm for Minimum Cycle Basis of Graphs
73. Altmetric Badge
    Chapter 72 The Black-Box Complexity of Nearest Neighbor Search
74. Altmetric Badge
    Chapter 73 Regular Solutions of Language Inequalities and Well Quasi-orders
75. Altmetric Badge
    Chapter 74 A Calculus of Coroutines
76. Altmetric Badge
    Chapter 75 Almost Optimal Decentralized Routing in Long-Range Contact Networks
77. Altmetric Badge
    Chapter 76 Word Problems on Compressed Words
78. Altmetric Badge
    Chapter 77 Complexity of Pseudoknot Prediction in Simple Models
79. Altmetric Badge
    Chapter 78 Property Testing of Regular Tree Languages
80. Altmetric Badge
    Chapter 79 Entropy as a Fixed Point
81. Altmetric Badge
    Chapter 80 Transparent Long Proofs: A First PCP Theorem for $\mbox{NP}_{\mathbb R}$
82. Altmetric Badge
    Chapter 81 A Time Lower Bound for Satisfiability
83. Altmetric Badge
    Chapter 82 Some Results on Effective Randomness
84. Altmetric Badge
    Chapter 83 A Polynomial Quantum Query Lower Bound for the Set Equality Problem
85. Altmetric Badge
    Chapter 84 Succinct Representations of Functions
86. Altmetric Badge
    Chapter 85 A Note on Karr’s Algorithm
87. Altmetric Badge
    Chapter 86 The Existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs
88. Altmetric Badge
    Chapter 87 Efficient Consistency Proofs for Generalized Queries on a Committed Database
89. Altmetric Badge
    Chapter 88 A $2 \frac{1}{8}$ -Approximation Algorithm for Rectangle Tiling
90. Altmetric Badge
    Chapter 89 Extensional Theories and Rewriting
91. Altmetric Badge
    Chapter 90 Hardness of String Similarity Search and Other Indexing Problems
92. Altmetric Badge
    Chapter 91 A Syntactic Characterization of Distributive LTL Queries
93. Altmetric Badge
    Chapter 92 Online Scheduling with Bounded Migration
94. Altmetric Badge
    Chapter 93 On the Expressive Power of Monadic Least Fixed Point Logic
95. Altmetric Badge
    Chapter 94 Counting in Trees for Free
96. Altmetric Badge
    Chapter 95 Games with Winning Conditions of High Borel Complexity
97. Altmetric Badge
    Chapter 96 Propositional PSPACE Reasoning with Boolean Programs Versus Quantified Boolean Formulas
98. Altmetric Badge
    Chapter 97 LA, Permutations, and the Hajós Calculus
99. Altmetric Badge
    Chapter 98 A Calibration of Ineffective Theorems of Analysis in a Hierarchy of Semi-classical Logical Principles
100. Altmetric Badge
     Chapter 99 Efficiently Computing Succinct Trade-Off Curves
101. Altmetric Badge
     Chapter 100 On Randomization Versus Synchronization in Distributed Systems
102. Altmetric Badge
     Chapter 101 A New Algorithm for Optimal Constraint Satisfaction and Its Implications
103. Altmetric Badge
     Chapter 102 On the Power of Ambainis’s Lower Bounds