×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
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] \scS. Collings, Improbable probabilities, to be published.
[4] \scJ. H. Conway, private communication.
[5] Feller, W, ()
[6] Gardner, M, On the paradoxical situations that arise from nontransitive relations, Sci. American, 120-125, (October 1974)
[7] \scI. P. Goulden and D. M. Jackson, An inversion theorem for cluster decomposition of sequences with distinguished subsequences, to be published. · 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; Guibas, L.J; Odlyzko, A.M, A new proof of the linearity of the boyer-Moore string searching algorithm, (), SIAM J. comput., 9, 672-682, (1980), also · 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] \scS.-Y. R. Li, A martingale scheme for studying the occurrence of sequence patterns in repeated experiments, to be published.
[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 Berlin/Heidelberg/New York · Zbl 0219.00003
[19] \scL. Ramshaw, private communication.
[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] \scJ. G. Wendel, private communication.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.