Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 43 Issue 6, Nov. 1996

Fast text searching for regular expressions or automaton searching on tries
Ricardo A. Baeza-Yates, Gaston H. Gonnet
Pages: 915-936
DOI: 10.1145/235809.235810
We present algorithms for efficient searching of regular expressions on preprocessed text, using a Patricia tree as a logical model for the index. We obtain searching algorithms that run in logarithmic expected time in the size of the text for a...

Constructing deterministic finite-state automata in recurrent neural networks
Christian W. Omlin, C. Lee Giles
Pages: 937-972
DOI: 10.1145/235809.235811
Recurrent neural networks that are trained to behave like deterministic finite-state automata (DFAs) can show deteriorating performance when tested on long strings. This deteriorating performance can be attributed to the...

Efficient routing in optical networks
Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan
Pages: 973-1001
DOI: 10.1145/235809.235812
This paper studies the problem of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by partitioning it into several channels, each at a different optical...

On the combinatorial and algebraic complexity of quantifier elimination
Saugata Basu, Richard Pollack, Marie-Françoise Roy
Pages: 1002-1045
DOI: 10.1145/235809.235813
In this paper, a new algorithm for performing quantifier elimination from first order formulas over real closed fields in given. This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this data....

An analysis of magic sets and related optimization strategies for logic queries
Seppo Sippu, Eljas Soisalon-Soininen
Pages: 1046-1088
DOI: 10.1145/235809.235814
We analyze the optimization effect of the “magic sets” rewriting technique for datalog queries and present some supplementary or alternative techniques that avoid many shortcomings of the basic technique. Given a magic sets rewritten...