String overlaps, pattern matching, and nontransitive games

DOI10.1016/0097-3165(81)90005-4zbMath0454.68109OpenAlexW2015569722WikidataQ57310986 ScholiaQ57310986MaRDI QIDQ1149796

Leonidas J. Guibas, Andrew M. Odlyzko

Publication date: 1981

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(81)90005-4

zbMATH Keywords

nontransitive dominance relations probabilistic coin-tossing game

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Enumerative combinatorics (05A99) Discrete mathematics in relation to computer science (68R99)

Related Items

Subsequence frequency in binary words, A characterization of the words occurring as factors in a minimum number of words, Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach, The Penney's game with group action, Analytic models and ambiguity of context-free languages, A limit theorem on the number of overlapping appearances of a pattern in a sequence of independent trials, Avoiding cross-bifix-free binary words, Learning Temporal Structures of Random Patterns by Generating Functions, On pattern occurrences in a random text, Reconstructing strings from substrings (Extended abstract), Deviations from uniformity in random strings, Binary vectors with prescribed subsets of consecutive ones, Random walks on \(Z^n_2\), The intersite distances between pattern occurrences in strings generated by general discrete- and continuous-time models: an algorithmic approach, The Number of Optimal Strategies in the Penney-Ante Game, Optimal Strategy for the First Player in the Penney Ante Game, Explicit distributional results in pattern formation, Binary words excluding a pattern and proper Riordan arrays, Applications of the theory of automata in enumeration, String matching and 1d lattice gases, On the Perron root and eigenvectors associated with a subshift of finite type, Successions in words and compositions, Permutations avoiding 1324 and patterns in Łukasiewicz paths, Large deviation properties for patterns, On volumes of spheres for the stem distance, Unnamed Item, Ranking graphs through hitting times of Markov chains, Construction of voting situations concordant with ranking patterns, Calculating the numbers of representations and the Garsia entropy in linear numeration systems, Ranking and unranking bordered and unbordered words, On the number of occurrences of a symbol in words of regular languages., A natural bijection for contiguous pattern avoidance in words, Entropy bounds for multi-word perturbations of subshifts, The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain, Construction of aggregation paradoxes through load-sharing models, On expected waiting time until given words appear in random sequence, SUBSHIFTS OF FINITE TYPE WITH A HOLE, Counting independent sets in Riordan graphs, First Occurrence in Pairs of Long Words: A Penney-ante Conjecture of Pevzner, Generating functions for lattice paths with several forbidden patterns, Periods in strings, A 2D non-overlapping code over a \(q\)-ary alphabet, Oscillation properties of expected stopping times and stopping probabilities for patterns consisting of consecutive states in Markov chains, Bijective proofs of some classical partition identities, Rarity and exponentiality: an extension of Keilson's theorem, with applications, Conway matrices related to a non-transitive head-or-tail game with a \(q\)-sided die and their Hamming weight-spectra via DFT and the MacWilliams duality formula, Where and when orbits of chaotic systems prefer to go, Optimal pattern matching algorithms, Multiple pattern matching: a Markov chain approach, On isomorphism classes of generalized Fibonacci cubes, Periodicity and repetitions in parameterized strings, On cyclic strings avoiding a pattern, Stochastic precedence and minima among dependent variables, Waiting times and stopping probabilities for patterns in Markov chains, Designing optimal- and fast-on-average pattern matching algorithms, Block-distribution in random strings, Where to place a hole to achieve a maximal escape rate, Statistical properties of factor oracles, String matching problems over free partially commutative monoids, How long does it take to see a flat Brownian path on the average?, Pattern correlation matrices and their properties, Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern, Frequency of symbol occurrences in bicomponent stochastic models, Border correlation of binary words, Pattern statistics and Vandermonde matrices., Long repetitive patterns in random sequences, Latent periodicity of serine-threonine and tyrosine protein kinases and other protein families, On the number of occurrences of sequence patterns, On the number of words containing the factor \((aba)^k\), Generalizations of the Goulden–Jackson cluster method, Patterns in Random Walks and Brownian Motion, Extension of Goulden–Jackson cluster method on pattern occurrences in random sequences and comparison with Régnier–Szpankowski method, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, The Goulden—Jackson cluster method: extensions, applications and implementations, Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata, Content-based networks: A pedagogical overview, On the waiting time till each of some given patterns occurs as a run, On Discrete Time Semi-Markov Chains and Applications in Words Occurrences, On the shape of the fringe of various types of random trees, Statistical Properties of Factor Oracles, Construction of the weight polynomial for autocorrelation of \(q\)-ary words, On enumeration of \(q\)-ary sequences with a fixed number of occurrences of the subblock 00, Gambling Teams and Waiting Times for Patterns in Two-State Markov Chains, Bivariate Markov chain embeddable variables of polynomial type, On occurrence of subpattern and method of gambling teams, Formulas for the numbers of sequences containing a given pattern given number of times, An asymptotically optimal layout for the shuffle-exchange graph, Combinatorial families that are exponentially far from being listable in Gray code sequence, On the number of word occurrences in a semi-Markov sequence of letters, A unified approach to word occurrence probabilities, The Goulden-Jackson cluster method for cyclic words, On the fair coin tossing process, Cross-monotone subsequences, Algebraic properties of cellular automata, Motif statistics., Unnamed Item, An analytical comparison of two string searching algorithms, Periodicity and Repetitions in Parameterized Strings, From Hertzsprung's problem to pattern-rewriting systems, The first return time test of pseudorandom numbers

Cites Work