Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 55 Issue 1, February 2008

Towards 3-query locally decodable codes of subexponential length
Sergey Yekhanin
Article No.: 1
DOI: 10.1145/1326554.1326555

A q-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit xi of the message by querying only...

On the minimization of XPath queries
S. Flesca, F. Furfaro, E. Masciari
Article No.: 2
DOI: 10.1145/1326554.1326556

XPath expressions define navigational queries on XML data and are issued on XML documents to select sets of element nodes. Due to the wide use of XPath, which is embedded into several languages for querying and manipulating XML data, the problem...

Bit complexity of breaking and achieving symmetry in chains and rings
Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum
Article No.: 3
DOI: 10.1145/1326554.1326557

We consider a failure-free, asynchronous message passing network with n links, where the processors are arranged on a ring or a chain. The processors are identically programmed but have distinct identities, taken from {0, 1,…...

A formal foundation for XrML
Joseph Y. Halpern, Vicky Weissman
Article No.: 4
DOI: 10.1145/1326554.1326558

XrML is becoming a popular language in industry for writing software licenses. The semantics for XrML is implicitly given by an algorithm that determines if a permission follows from a set of licenses. We focus on a fragment of the language and...

Undecidability of bisimilarity by defender's forcing
Petr Jančar, Jivří Srba
Article No.: 5
DOI: 10.1145/1326554.1326559

Stirling [1996, 1998] proved the decidability of bisimilarity on so-called normed pushdown processes. This result was substantially extended by Sénizergues [1998, 2005] who showed the decidability of bisimilarity for...