LIPIcs.ESA.2018.45.pdf
- Filesize: 442 kB
- 13 pages
Document
On the Decision Tree Complexity of String Matching
Authors
-
Part of:
Volume:
26th Annual European Symposium on Algorithms (ESA 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-08-14
Cite AsGet 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
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)
0PDF Downloads
References
-
M. Artin. Algebra. Pearson Prentice Hall, 2011.
-
J. Berstel and J. Karhumäki. Combinatorics on words - a tutorial. Bulletin EATCS, pages 178-228, February 2003.
-
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction To Algorithms. MIT Press, 2001.
- 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.
-
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.