↓ 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 Holographic Circuits
  3. Altmetric Badge
    Chapter 2 Probabilistic Polynomial-Time Semantics for a Protocol Security Logic
  4. Altmetric Badge
    Chapter 3 A Gentle Introduction to Semantic Subtyping
  5. Altmetric Badge
    Chapter 4 Logics for Unranked Trees: An Overview
  6. Altmetric Badge
    Chapter 5 Automata, Languages and Programming
  7. Altmetric Badge
    Chapter 6 The Tree Inclusion Problem: In Optimal Space and Faster
  8. Altmetric Badge
    Chapter 7 Union-Find with Constant Time Deletions
  9. Altmetric Badge
    Chapter 8 Optimal In-place Sorting of Vectors and Records
  10. Altmetric Badge
    Chapter 9 Towards Optimal Multiple Selection
  11. Altmetric Badge
    Chapter 10 Simple Extractors via Constructions of Cryptographic Pseudo-random Generators
  12. Altmetric Badge
    Chapter 11 Bounds on the Efficiency of “Black-Box” Commitment Schemes
  13. Altmetric Badge
    Chapter 12 On Round-Efficient Argument Systems
  14. Altmetric Badge
    Chapter 13 Computational Bounds on Hierarchical Data Processing with Applications to Information Security
  15. Altmetric Badge
    Chapter 14 Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins
  16. Altmetric Badge
    Chapter 15 Worst Case Optimal Union-Intersection Expression Evaluation
  17. Altmetric Badge
    Chapter 16 Measure and Conquer: Domination – A Case Study
  18. Altmetric Badge
    Chapter 17 Optimistic Asynchronous Atomic Broadcast
  19. Altmetric Badge
    Chapter 18 Asynchronous Perfectly Secure Communication over One-Time Pads
  20. Altmetric Badge
    Chapter 19 Single-Prover Concurrent Zero Knowledge in Almost Constant Rounds
  21. Altmetric Badge
    Chapter 20 LCA Queries in Directed Acyclic Graphs
  22. Altmetric Badge
    Chapter 21 Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs
  23. Altmetric Badge
    Chapter 22 Deterministic Constructions of Approximate Distance Oracles and Spanners
  24. Altmetric Badge
    Chapter 23 An Õ(m 2 n) Randomized Algorithm to Compute a Minimum Cycle Basis of a Directed Graph
  25. Altmetric Badge
    Chapter 24 Basing Cryptographic Protocols on Tamper-Evident Seals
  26. Altmetric Badge
    Chapter 25 Hybrid Trapdoor Commitments and Their Applications
  27. Altmetric Badge
    Chapter 26 On Steganographic Chosen Covertext Security
  28. Altmetric Badge
    Chapter 27 Classification of Boolean Functions of 6 Variables or Less with Respect to Some Cryptographic Properties
  29. Altmetric Badge
    Chapter 28 Label-Guided Graph Exploration by a Finite Automaton
  30. Altmetric Badge
    Chapter 29 On the Wake-Up Problem in Radio Networks
  31. Altmetric Badge
    Chapter 30 Distance Constrained Labelings of Graphs of Bounded Treewidth
  32. Altmetric Badge
    Chapter 31 Optimal Branch-Decomposition of Planar Graphs in O(n 3) Time
  33. Altmetric Badge
    Chapter 32 NFAs With and Without ε-Transitions
  34. Altmetric Badge
    Chapter 33 On the Equivalence of ${\mathbb Z}$ -Automata
  35. Altmetric Badge
    Chapter 34 A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata
  36. Altmetric Badge
    Chapter 35 Groupoids That Recognize Only Regular Languages
  37. Altmetric Badge
    Chapter 36 Append-Only Signatures
  38. Altmetric Badge
    Chapter 37 Hierarchical Group Signatures
  39. Altmetric Badge
    Chapter 38 Designated Verifier Signature Schemes: Attacks, New Security Notions and a New Construction
  40. Altmetric Badge
    Chapter 39 Single-Key AIL-MACs from Any FIL-MAC
  41. Altmetric Badge
    Chapter 40 The Efficiency and Fairness of a Fixed Budget Resource Allocation Game
  42. Altmetric Badge
    Chapter 41 Braess’s Paradox, Fibonacci Numbers, and Exponential Inapproximability
  43. Altmetric Badge
    Chapter 42 Weighted Automata and Weighted Logics
  44. Altmetric Badge
    Chapter 43 Restricted Two-Variable FO + MOD Sentences, Circuits and Communication Complexity
  45. Altmetric Badge
    Chapter 44 Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of Type y 2=x $^{\rm 2{\it k}+1}$ +ax
  46. Altmetric Badge
    Chapter 45 Solvability of a System of Bivariate Polynomial Equations over a Finite Field
  47. Altmetric Badge
    Chapter 46 Cache-Oblivious Planar Shortest Paths
  48. Altmetric Badge
    Chapter 47 Cache-Aware and Cache-Oblivious Adaptive Sorting
  49. Altmetric Badge
    Chapter 48 Simulated Annealing Beats Metropolis in Combinatorial Optimization
  50. Altmetric Badge
    Chapter 49 Online Interval Coloring and Variants
  51. Altmetric Badge
    Chapter 50 Automata, Languages and Programming
  52. Altmetric Badge
    Chapter 51 Reordering Buffer Management for Non-uniform Cost Models
  53. Altmetric Badge
    Chapter 52 Combining Intruder Theories
  54. Altmetric Badge
    Chapter 53 Computationally Sound Implementations of Equational Theories Against Passive Adversaries
  55. Altmetric Badge
    Chapter 54 Password-Based Encryption Analyzed
  56. Altmetric Badge
    Chapter 55 On the Cover Time of Random Geometric Graphs
  57. Altmetric Badge
    Chapter 56 On the Existence of Hamiltonian Cycles in Random Intersection Graphs
  58. Altmetric Badge
    Chapter 57 Optimal Cover Time for a Graph-Based Coupon Collector Process
  59. Altmetric Badge
    Chapter 58 Stability and Similarity of Link Analysis Ranking Algorithms
  60. Altmetric Badge
    Chapter 59 Up-to Techniques for Weak Bisimulation
  61. Altmetric Badge
    Chapter 60 Petri Algebras
  62. Altmetric Badge
    Chapter 61 A Finite Basis for Failure Semantics
  63. Altmetric Badge
    Chapter 62 Spatial Logics for Bigraphs
  64. Altmetric Badge
    Chapter 63 Completely Non-malleable Schemes
  65. Altmetric Badge
    Chapter 64 Boneh-Franklin Identity Based Encryption Revisited
  66. Altmetric Badge
    Chapter 65 Single-Database Private Information Retrieval with Constant Communication Rate
  67. Altmetric Badge
    Chapter 66 Concurrent Zero Knowledge in the Public-Key Model
  68. Altmetric Badge
    Chapter 67 Automata, Languages and Programming
  69. Altmetric Badge
    Chapter 68 Polynomial Time Preemptive Sum-Multicoloring on Paths
  70. Altmetric Badge
    Chapter 69 The Generalized Deadlock Resolution Problem
  71. Altmetric Badge
    Chapter 70 Facility Location in Sublinear Time
  72. Altmetric Badge
    Chapter 71 The Complexity of Stochastic Rabin and Streett Games
  73. Altmetric Badge
    Chapter 72 Recursive Markov Decision Processes and Recursive Stochastic Games
  74. Altmetric Badge
    Chapter 73 Decidability in Syntactic Control of Interference
  75. Altmetric Badge
    Chapter 74 Idealized Algol with Ground Recursion, and DPDA Equivalence
  76. Altmetric Badge
    Chapter 75 From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem
  77. Altmetric Badge
    Chapter 76 How Well Can Primal-Dual and Local-Ratio Algorithms Perform?
  78. Altmetric Badge
    Chapter 77 Approximating Max kCSP – Outperforming a Random Assignment with Almost a Linear Factor
  79. Altmetric Badge
    Chapter 78 On Dynamic Bit-Probe Complexity
  80. Altmetric Badge
    Chapter 79 Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines
  81. Altmetric Badge
    Chapter 80 Lower Bounds for Circuits with Few Modular and Symmetric Gates
  82. Altmetric Badge
    Chapter 81 Discrete Random Variables over Domains
  83. Altmetric Badge
    Chapter 82 An Accessible Approach to Behavioural Pseudometrics
  84. Altmetric Badge
    Chapter 83 Noisy Turing Machines
  85. Altmetric Badge
    Chapter 84 A Better Approximation Ratio for the Vertex Cover Problem
  86. Altmetric Badge
    Chapter 85 Stochastic Steiner Trees Without a Root
  87. Altmetric Badge
    Chapter 86 Approximation Algorithms for the Max-coloring Problem
  88. Altmetric Badge
    Chapter 87 Tight Lower Bounds for Query Processing on Streaming and External Memory Data
  89. Altmetric Badge
    Chapter 88 Decidability and Complexity Results for Timed Automata via Channel Machines
  90. Altmetric Badge
    Chapter 89 Congruences for Visibly Pushdown Languages
  91. Altmetric Badge
    Chapter 90 Approximation Algorithms for Euclidean Group TSP
  92. Altmetric Badge
    Chapter 91 Influential Nodes in a Diffusion Model for Social Networks
  93. Altmetric Badge
    Chapter 92 Automata, Languages and Programming
  94. Altmetric Badge
    Chapter 93 New Approaches for Virtual Private Network Design
  95. Altmetric Badge
    Chapter 94 Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity
  96. Altmetric Badge
    Chapter 95 Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
  97. Altmetric Badge
    Chapter 96 On the l-Ary GCD-Algorithm in Rings of Integers
  98. Altmetric Badge
    Chapter 97 A Fully Abstract Encoding of the π-Calculus with Data Terms
  99. Altmetric Badge
    Chapter 98 Orthogonal Extensions in Structural Operational Semantics
  100. Altmetric Badge
    Chapter 99 Basic Observables for a Calculus for Global Computing
  101. Altmetric Badge
    Chapter 100 Compositional Verification of Asynchronous Processes via Constraint Solving
  102. Altmetric Badge
    Chapter 101 Optimal Spaced Seeds for Faster Approximate String Matching
  103. Altmetric Badge
    Chapter 102 Fast Neighbor Joining
  104. Altmetric Badge
    Chapter 103 Randomized Fast Design of Short DNA Words
  105. Altmetric Badge
    Chapter 104 A Quantum Lower Bound for the Query Complexity of Simon’s Problem
  106. Altmetric Badge
    Chapter 105 All Quantum Adversary Methods Are Equivalent
  107. Altmetric Badge
    Chapter 106 Quantum Complexity of Testing Group Commutativity
  108. Altmetric Badge
    Chapter 107 Semantic-Based Code Obfuscation by Abstract Interpretation
  109. Altmetric Badge
    Chapter 108 About Hoare Logics for Higher-Order Store
  110. Altmetric Badge
    Chapter 109 The Polyranking Principle
  111. Altmetric Badge
    Chapter 110 Approximate Guarding of Monotone and Rectilinear Polygons
  112. Altmetric Badge
    Chapter 111 Linear Time Algorithms for Clustering Problems in Any Dimensions
  113. Altmetric Badge
    Chapter 112 Automata, Languages and Programming
  114. Altmetric Badge
    Chapter 113 On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group
  115. Altmetric Badge
    Chapter 114 On the Hardness of Embeddings Between Two Finite Metrics
  116. Altmetric Badge
    Chapter 115 Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval
  117. Altmetric Badge
    Chapter 116 Automata, Languages and Programming
  118. Altmetric Badge
    Chapter 117 Unsafe Grammars and Panic Automata
  119. Altmetric Badge
    Chapter 118 Signaling P Systems and Verification Problems
Attention for Chapter 43: Restricted Two-Variable FO + MOD Sentences, Circuits and Communication Complexity
Altmetric Badge

Citations

dimensions_citation
9 Dimensions

Readers on

mendeley
23 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.
Chapter title
Restricted Two-Variable FO + MOD Sentences, Circuits and Communication Complexity
Chapter number 43
Book title
Automata, Languages and Programming
Published by
Springer, Berlin, Heidelberg, July 2005
DOI 10.1007/11523468_43
Book ISBNs
978-3-54-027580-0, 978-3-54-031691-6
Authors

Pascal Tesson, Denis Thérien

Mendeley readers

Mendeley readers

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

Geographical breakdown

Country Count As %
Unknown 23 100%

Demographic breakdown

Readers by professional status Count As %
Student > Ph. D. Student 7 30%
Student > Master 6 26%
Researcher 3 13%
Professor 2 9%
Lecturer 1 4%
Other 2 9%
Unknown 2 9%
Readers by discipline Count As %
Computer Science 19 83%
Mathematics 1 4%
Physics and Astronomy 1 4%
Unknown 2 9%