×

String overlaps, pattern matching, and nontransitive games. (English) Zbl 0454.68109


MSC:

68T10 Pattern recognition, speech recognition
68R99 Discrete mathematics in relation to computer science
05A99 Enumerative combinatorics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ankeny, N. C.; Brauer, R.; Chowla, S., A note on the class-numbers of algebraic number fields, Amer. J. Math., 78, 51-61 (1956) · Zbl 0074.26502
[2] Boyer, R. S.; Moore, J. S., A fast string searching algorithm, Comm. ACM, 20, 762-772 (1977) · Zbl 1219.68165
[3] S. Collings; S. Collings
[4] J. H. Conway, private communication; J. H. Conway, private communication
[5] Feller, W., (An Introduction to Probability Theorey and Its Applications, Vol. 1 (1968), Wiley: Wiley New York) · Zbl 0155.23101
[6] Gardner, M., On the paradoxical situations that arise from nontransitive relations, Sci. American, 120-125 (October 1974)
[7] I. P. Goulden and D. M. Jackson; I. P. Goulden and D. M. Jackson · Zbl 0467.05008
[8] Guibas, L. J.; Odlyzko, A. M., Periods in strings, J. Comb. Theory (A), 30, 19-42 (1981) · Zbl 0464.68070
[9] Guibas, L. J.; Odlyzko, A. M., Maximal prefix-synchronized codes, SIAM J. Appl. Math., 35, 401-418 (1978) · Zbl 0394.94024
[10] Guibas, L. J.; Odlyzko, A. M., SIAM J. Comput., 9, 672-682 (1980) · Zbl 0446.68050
[11] Harborth, H., Endliche 0-1-Folgen mit gleichen Teilblöcken, J. Reine Angew. Math., 271, 139-154 (1974) · Zbl 0297.05008
[12] Kim, K. H.; Putcha, M. S.; Roush, F. W., Some combinatorial properties of free seimgroups, J. London Math. Soc. (2), 16, 397-402 (1977) · Zbl 0368.20036
[13] Knuth, D. E.; Morris, J. H.; Pratt, V. R., Fast pattern matching in strings, SIAM J. Comput., 6, 323-350 (1977) · Zbl 0372.68005
[14] Leslie, R. T., Recurrent composite events, J. Appl. Prob., 4, 34-61 (1967) · Zbl 0178.19702
[15] S.-Y. R. Li; S.-Y. R. Li
[16] Nielsen, P. T., On the expected duration of a search for a fixed pattern in random data, IEEE Trans. Inform. Theory, 702-704 (1973), IT-19 · Zbl 0278.94008
[17] Penney, W., Problem: penney-ante, J. Recreational Math., 2, 241 (1969)
[18] Polya, G.; Szegő, G., Aufgaben and Lehrsätze aus der Analysis II, 4. Auflage (1971), Springer-Verlag: Springer-Verlag Berlin/Heidelberg/New York · Zbl 0219.00003
[19] L. Ramshaw; L. Ramshaw
[20] Rivest, R. L., On the worst-case behavior of string-searching algorithms, SIAM J. Comp., 6, 669-674 (1977) · Zbl 0366.68032
[21] Roberts, S. W., Properties of control chart zone tests, Bell System Tech. J., 37, 83-114 (1958)
[22] Roberts, S. W., On the first occurrence of any of a selected set of outcome patterns in a sequence of repeated trials (1963), unpublished manuscript
[23] Saperstein, B., Note on a clustering problem, J. Appl. Prob., 12, 629-632 (1975) · Zbl 0335.60006
[24] Solov’ev, A. D., A combinatorial identity and its application to the problem concerning the first occurrence of a ratre event, Theory Prob. Appl., 11, 276-282 (1966) · Zbl 0154.43104
[25] Tenney, R. L.; Foster, C. C., Nontransitive dominance, Math. Mag., 49, 115-120 (1976)
[26] J. G. Wendel; J. G. Wendel
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.