↓ Skip to main content

Automata, Languages and Programming

Overview of attention for book
Cover of '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
Overall attention for this book and its chapters
Altmetric Badge

Mentioned by

twitter
2 X users
wikipedia
2 Wikipedia pages
q&a
2 Q&A threads

Citations

dimensions_citation
7 Dimensions

Readers on

mendeley
17 Mendeley
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Title
Automata, Languages and Programming
Published by
Springer, Berlin, Heidelberg, January 2004
DOI 10.1007/b99859
ISBNs
978-3-54-022849-3, 978-3-54-027836-8
Editors

Josep Díaz, Juhani Karhumäki, Arto Lepistö, Donald Sannella

X Demographics

X Demographics

The data shown below were collected from the profiles of 2 X users who shared this research output. Click here to find out more about how the information was compiled.
Mendeley readers

Mendeley readers

The data shown below were compiled from readership statistics for 17 Mendeley readers of this research output. Click here to see the associated Mendeley record.

Geographical breakdown

Country Count As %
Unknown 17 100%

Demographic breakdown

Readers by professional status Count As %
Professor > Associate Professor 1 6%
Unknown 16 94%
Readers by discipline Count As %
Mathematics 1 6%
Unknown 16 94%