Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 49 Issue 4, July 2002

Qualitative decision theory: from savage's axioms to nonmonotonic reasoning
Didier Dubois, Hélène Fargier, Henri Prade, Patrice Perny
Pages: 455-495
DOI: 10.1145/581771.581772
This paper investigates to what extent a purely symbolic approach to decision making under uncertainty is possible, in the scope of artificial intelligence. Contrary to classical approaches to decision theory, we try to rank acts without resorting to...

Dense quantum coding and quantum finite automata
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh Vazirani
Pages: 496-511
DOI: 10.1145/581771.581773
We consider the possibility of encoding m classical bits into many fewer n quantum bits (qubits) so that an arbitrary bit from the original m bits can be recovered with good probability. We show that nontrivial quantum codes...

On the complexity analysis of static analyses
David McAllester
Pages: 512-537
DOI: 10.1145/581771.581774
This paper argues that for many algorithms, and static analysis algorithms in particular, bottom-up logic program presentations are clearer and simpler to analyze, for both correctness and complexity, than classical pseudo-code presentations....

Formal verification of standards for distance vector routing protocols
Karthikeyan Bhargavan, Davor Obradovic, Carl A. Gunter
Pages: 538-576
DOI: 10.1145/581771.581775
We show how to use an interactive theorem prover, HOL, together with a model checker, SPIN, to prove key properties of distance vector routing protocols. We do three case studies: correctness of the RIP standard, a sharp real-time bound on RIP...