Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 47 Issue 3, May 2000

A subdivision-based algorithm for the sparse resultant
John F. Canny, Ioannis Z. Emiris
Pages: 417-451
DOI: 10.1145/337244.337247
Multivariate resultants generalize the Sylvester resultant of two polynomials and characterize the solvability of a polynomial system. They also reduce the computation of all common roots to a problem in linear algebra. We propose a...

An axiomatic treatment of three qualitative decision criteria
Ronen I. Brafman, Moshe Tennenholtz
Pages: 452-482
DOI: 10.1145/337244.337251
The need for computationally efficient decision-making techniques together with the desire to simplify the processes of knowledge acquisition and agent specification have led various researchers in artificial intelligence to examine qualitative...

The expressibility of languages and relations by word equations
Juhani Karhumäki, Filippo Mignosi, Wojciech Plandowski
Pages: 483-505
DOI: 10.1145/337244.337255
Classically, several properties and relations of words, such as “being a power of the same word” can be expressed by using word equations. This paper is devoted to a general study of the expressive power of word equations. As main...

Learning functions represented as multiplicity automata
Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, Stefano Varricchio
Pages: 506-530
DOI: 10.1145/337244.337257
We study the learnability of multiplicity automata in Angluin's exact learning model, and we investigate its applications. Our starting point is a known theorem from automata theory relating the number of states in a minimal...

Behavioral equivalence in the polymorphic pi-calculus
Benjamin C. Pierce, Davide Sangiorgi
Pages: 531-584
DOI: 10.1145/337244.337261
We investigate parametric polymorphism in message-based concurrent programming, focusing on behavioral equivalences in a typed process calculus analogous to the polymorphic lambda-calculus of Girard and Reynolds....