Arrow Research search

Author name cluster

Alain J. Mayer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers
2 author rows

Possible papers

5

TCS Journal 1996 Journal Article

The complexity of PDL with interleaving

  • Alain J. Mayer
  • Larry J. Stockmeyer

To provide a logic for reasoning about concurrently executing programs, Abrahamson has defined an extension of propositional dynamic logic (PDL) by allowing interleaving as an operator for combining programs, in addition to the regular PDL operators union, concatenation, and star. We show that the satisfiability problem for interleaving PDL is complete for deterministic double-exponential time, and that this problem requires time double-exponential in cn log n for some positive constant c. Moreover, this lower bound holds even when restricted to formulas where each program appearing in the formula has the form a1¦a2¦ … ¦ak where ¦ denotes the interleaving operator and where a 1, …, a k are regular programs, i. e. , programs built from atomic programs using only the regular operators. Another consequence of the method used to prove this result is that the equivalence problem for regular expressions with interleaving requires space 2 cn log n and that this lower bound holds even to decide whether (E1¦E2¦ … ¦Ek) ∪ F ≡ ∑∗ where E 1, …, E k, F are ordinary regular expressions; this improves a previous result of the authors. Moreover, the same lower bound holds for the containment problem for expressions of the form E1¦E2¦ … ¦Ek.

Details DOI

FOCS Conference 1995 Conference Paper

Resolving Message Complexity of Byzantine Agreement and beyond

  • Zvi Galil
  • Alain J. Mayer
  • Moti Yung

Byzantine Agreement among processors is a basic primitive in distributed computing. It comes in a number of basic fault models: "Crash", "Omission" and "Malicious" adversarial behaviors. The message complexity of the primitive has been known for the strong failure models of Malicious and Omission adversary since the early 80's, while the question for the more benign Crash failure model has been open. We show how to solve agreement in the presence of crash failures using O(n) messages which is optimal, thus settling a thirteen year old open problem. Our solution has almost linear time and our new algorithmic techniques have further implications: a family of "early stopping" agreement protocols with improved message-complexity; and a new solution to "Checkpoint" yielding a substantial improvement of the protocol for distributed work performance under adaptive parallelism in a network of workstations.

Details
v2026.09.13