ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Faster tree pattern matching
Full text PdfPdf (501 KB)
Source Journal of the ACM (JACM) archive
Volume 41 ,  Issue 2  (March 1994) table of contents
Pages: 205 - 213  
Year of Publication: 1994
ISSN:0004-5411
Authors
Moshe Dubiner  Tel-Aviv Univ., Tel-Aviv, Israel
Zvi Galil  Tel-Aviv Univ., Tel-Aviv, Israel and Columbia Univ., New York, NY
Edith Magen  Tel-Aviv Univ., Tel-Aviv, Israel
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 2,   Downloads (12 Months): 64,   Citation Count: 4
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/174652.174653
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
~FISCHER, M. J., AND PATERSON, M. S. 1974. String-matching and other products. In Proceediugs ~of the S1A M ~4MS Symposlum on Complexity of Computation, R. M. Karp, ed. SIAM, New York, ~pp. 113-125.
2
Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982  [doi>10.1145/322290.322295]
 
3
~KNUTH, D. E., MORRIS, J. H. AND PRATT, V. R. 1977. Fast pattern matching in strings. SIAMJ. ~Comp, 6, 323-350.
 
4
~KOSARAJU, S. R. 1989. Efficient tree pattern matching. In Proc'eedtngs of the 30th a~znztal IEEE ~Sylll{)OXlllDl Oil Fottlldgt{otls of COltlplt~F Science. I{EEE, New York, pp. 178-183.

CITED BY  4
Cedric Chauve, Tree pattern matching with a more general notion of occurrence of the pattern, Information Processing Letters, v.82 n.4, p.197-201, 31 May 2002
Giorgio Satta , Eric Brill, Efficient transformation-based parsing, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.255-262, June 24-27, 1996, Santa Cruz, California
Richard Cole , Ramesh Hariharan , Piotr Indyk, Tree pattern matching and subset matching in deterministic O(n log3 n)-time, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.245-254, January 17-19, 1999, Baltimore, Maryland, United States
Liang Zuopeng , Hu Kongfa , Ye Ning , Dong Yisheng, An efficient index structure for XML based on generalized suffix tree, Information Systems, v.32 n.2, p.283-294, April, 2007

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees


General Terms:
Algorithms, Theory


Keywords:
convolution, don't-care, pattern matching, period, string matching, tree

Collaborative Colleagues:
Moshe Dubiner: colleagues
Zvi Galil: colleagues
Edith Magen: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player