Document Open Access Logo

On the Decision Tree Complexity of String Matching

Authors Xiaoyu He, Neng Huang, Xiaoming Sun

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.45.pdf
  • Filesize: 442 kB
  • 13 pages

Document Identifiers

Author Details

Xiaoyu He
  • Institute of Computing Technology, Chinese Academy of Sciences, China, and, University of Chinese Academy of Sciences, China
Neng Huang
  • University of Chinese Academy of Sciences, China
Xiaoming Sun
  • Institute of Computing Technology, Chinese Academy of Sciences, China, and , University of Chinese Academy of Sciences, China

Funding

This work was supported in part by the National Natural Science Foundation of China Grant 61433014, 61502449, 61602440, and the 973 Program of China Grants No.2016YFB1000201.

Cite As Get BibTex

Xiaoyu He, Neng Huang, and Xiaoming Sun. On the Decision Tree Complexity of String Matching. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 45:1-45:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.45

Abstract

String matching is one of the most fundamental problems in computer science. A natural problem is to determine the number of characters that need to be queried (i.e. the decision tree complexity) in a string in order to decide whether this string contains a certain pattern. Rivest showed that for every pattern p, in the worst case any deterministic algorithm needs to query at least n-|p|+1 characters, where n is the length of the string and |p| is the length of the pattern. He further conjectured that this bound is tight. By using the adversary method, Tuza disproved this conjecture and showed that more than one half of binary patterns are evasive, i.e. any algorithm needs to query all the characters (see Section 1.1 for more details).
In this paper, we give a query algorithm which settles the decision tree complexity of string matching except for a negligible fraction of patterns. Our algorithm shows that Tuza's criteria of evasive patterns are almost complete. Using the algebraic approach of Rivest and Vuillemin, we also give a new sufficient condition for the evasiveness of patterns, which is beyond Tuza's criteria. In addition, our result reveals an interesting connection to Skolem's Problem in mathematics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Oracles and decision trees
Keywords
  • String Matching
  • Decision Tree Complexity
  • Boolean Function
  • Algebraic Method

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. M. Artin. Algebra. Pearson Prentice Hall, 2011. Google Scholar
  2. J. Berstel and J. Karhumäki. Combinatorics on words - a tutorial. Bulletin EATCS, pages 178-228, February 2003. Google Scholar
  3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction To Algorithms. MIT Press, 2001. Google Scholar
  4. Z. Galil and J. Seiferas. Time-space-optimal string matching. Journal of Computer and System Sciences, 26(3):280-294, 1983. URL: http://dx.doi.org/10.1016/0022-0000(83)90002-8.
  5. V. Halava, T. Harju, M. Hirvensalo, and J. Karhumäki. Skolem’s problem - on the border between decidability and undecidability. TUCS Technical Reports 683, 2005. Google Scholar
  6. R. M. Karp and M. O. Rabin. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, 31(2):249-260, 1987. URL: http://dx.doi.org/10.1147/rd.312.0249.
  7. D. Knuth, J. Morris, and V. Pratt. Fast Pattern Matching in Strings. SIAM Journal on Computing, 6(2):323-350, jun 1977. URL: http://dx.doi.org/10.1137/0206024.
  8. P. Nielsen. A note on bifix-free sequences (Corresp.). IEEE Transactions on Information Theory, 19(5):704-706, 1973. URL: http://dx.doi.org/10.1109/TIT.1973.1055065.
  9. R. L. Rivest. On the Worst-Case Behavior of String-Searching Algorithms. SIAM Journal on Computing, 6(4):669-674, 1977. URL: http://dx.doi.org/10.1137/0206048.
  10. R. L. Rivest and J. Vuillemin. A Generalization and Proof of the Aanderaa-Rosenberg Conjecture. In Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, STOC '75, pages 6-11, New York, NY, USA, 1975. ACM. URL: http://dx.doi.org/10.1145/800116.803747.
  11. Z. Tuza. Worst-case behavior of string-searching algorithms. Journal of Statistical Planning and Inference, 6(1):99-103, 1982. URL: http://dx.doi.org/10.1016/0378-3758(82)90060-X.
  12. A. Yao. The Complexity of Pattern Matching for a Random String. SIAM Journal on Computing, 8(3):368-387, 1979. URL: http://dx.doi.org/10.1137/0208029.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact