Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 59 Issue 1, February 2012

Probabilistic ω-automata
Christel Baier, Marcus Grösser, Nathalie Bertrand
Article No.: 1
DOI: 10.1145/2108242.2108243

Probabilistic ω-automata are variants of nondeterministic automata over infinite words where all choices are resolved by probabilistic distributions. Acceptance of a run for an infinite input word can be defined using traditional acceptance...

Polylogarithmic concurrent data structures from monotone circuits
James Aspnes, Hagit Attiya, Keren Censor-Hillel
Article No.: 2
DOI: 10.1145/2108242.2108244

This article presents constructions of useful concurrent data structures, including max registers and counters, with step complexity that is sublinear in the number of processes, n. This result avoids a well-known lower bound by having step...

New combinatorial topology bounds for renaming: The upper bound
Armando Castañeda, Sergio Rajsbaum
Article No.: 3
DOI: 10.1145/2108242.2108245

In the renaming task, n+1 processes start with unique input names from a large space and must choose unique output names taken from a smaller name space, 0,1,…, K. To rule out trivial solutions, a protocol must be...

Invited article foreword
Victor Vianu
Article No.: 4
DOI: 10.1145/2108242.2108246

Highly acyclic groups, hypergraph covers, and the guarded fragment
Martin Otto
Article No.: 5
DOI: 10.1145/2108242.2108247

We construct finite groups whose Cayley graphs have large girth even with respect to a discounted distance measure that contracts arbitrarily long sequences of edges from the same color class (subgroup), and only counts transitions between color...