enter search term and/or author name
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
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
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...
Highly acyclic groups, hypergraph covers, and the guarded fragment
Article No.: 5
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...