Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 61 Issue 2, April 2014

Space-Efficient Frameworks for Top-k String Retrieval
Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan, Jeffrey Scott Vitter
Article No.: 9
DOI: 10.1145/2590774

The inverted index is the backbone of modern web search engines. For each word in a collection of web documents, the index records the list of documents where this word occurs. Given a set of query words, the job of a search engine is to output a...

Avoiding Three Consecutive Blocks of the Same Size and Same Sum
Julien Cassaigne, James D. Currie, Luke Schaeffer, Jeffrey Shallit
Article No.: 10
DOI: 10.1145/2590775

We show that there exists an infinite word over the alphabet {0, 1, 3, 4} containing no three consecutive blocks of the same size and the same sum. This answers an open problem of Pirillo and Varricchio from 1994.


Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces
Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio
Article No.: 11
DOI: 10.1145/2590772

The Chow parameters of a Boolean function f:{−1, 1}n → {−1, 1} are its n+1 degree-0 and degree-1 Fourier coefficients. It has been known since 1961 [Chow 1961;...

XML Schema Mappings: Data Exchange and Metadata Management
Shun'ichi Amano, Claire David, Leonid Libkin, Filip Murlak
Article No.: 12
DOI: 10.1145/2590773

Relational schema mappings have been extensively studied in connection with data integration and exchange problems, but mappings between XML schemas have not received the same amount of attention. Our goal is to develop a theory of expressive XML...

Beyond Lamport's Happened-before: On Time Bounds and the Ordering of Events in Distributed Systems
Ido Ben-Zvi, Yoram Moses
Article No.: 13
DOI: 10.1145/2542181

The coordination of a sequence of actions, to be performed in a linear temporal order in a distributed system, is studied. While in asynchronous message-passing systems such ordering of events requires the construction of message chains based on...

Undecidability of Propositional Separation Logic and Its Neighbours
James Brotherston, Max Kanovich
Article No.: 14
DOI: 10.1145/2542667

In this article, we investigate the logical structure of memory models of theoretical and practical interest. Our main interest is in “the logic behind a fixed memory model”, rather than in “a model of any kind behind a given...