String overlaps, pattern matching, and nontransitive games
From MaRDI portal
Publication:1149796
DOI10.1016/0097-3165(81)90005-4zbMATH Open0454.68109OpenAlexW2015569722WikidataQ57310986 ScholiaQ57310986MaRDI QIDQ1149796FDOQ1149796
Authors: Leonidas Guibas, Andrew 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
Enumerative combinatorics (05A99) Pattern recognition, speech recognition (68T10) Discrete mathematics in relation to computer science (68R99)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Note on the Class-Numbers of Algebraic Number Fields
- A fast string searching algorithm
- Fast Pattern Matching in Strings
- Some Combinatorial Properties of Free Semigroups
- An Inversion Theorem for Cluster Decompositions of Sequences with Distinguished Subsequences
- Recurrent composite events
- A Combinatorial Identity and Its Application to the Problem Concerning the First Occurrence of a Rare Event
- Periods in strings
- Maximal Prefix-Synchronized Codes
- On the Worst-Case Behavior of String-Searching Algorithms
- Non-Transitive Dominance
- A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm
- Endliche 0-1-Folgen mit gleichen Teilblöcken.
- Note on a clustering problem
- On the expected duration of a search for a fixed pattern in random data (Corresp.)
Cited In (only showing first 100 items - show all)
- Periods in strings
- Algebraic properties of cellular automata
- Large deviation properties for patterns
- Block-distribution in random strings
- Statistical properties of factor oracles
- Generating functions for lattice paths with several forbidden patterns
- Binary vectors with prescribed subsets of consecutive ones
- Applications of the theory of automata in enumeration
- Explicit distributional results in pattern formation
- An asymptotically optimal layout for the shuffle-exchange graph
- Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern
- Random walks on \(Z^n_2\)
- Analytic models and ambiguity of context-free languages
- Multiple pattern matching: a Markov chain approach
- Frequency of symbol occurrences in bicomponent stochastic models
- Border correlation of binary words
- Long repetitive patterns in random sequences
- Binary words excluding a pattern and proper Riordan arrays
- Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach
- A limit theorem on the number of overlapping appearances of a pattern in a sequence of independent trials
- On occurrence of subpattern and method of gambling teams
- A 2D non-overlapping code over a \(q\)-ary alphabet
- On the number of words containing the factor \((aba)^k\)
- On the number of occurrences of sequence patterns
- A unified approach to word occurrence probabilities
- On the number of occurrences of a symbol in words of regular languages.
- Avoiding cross-bifix-free binary words
- Latent periodicity of serine-threonine and tyrosine protein kinases and other protein families
- Motif statistics.
- String matching and 1d lattice gases
- Successions in words and compositions
- On the shape of the fringe of various types of random trees
- Deviations from uniformity in random strings
- On pattern occurrences in a random text
- On Discrete Time Semi-Markov Chains and Applications in Words Occurrences
- On volumes of spheres for the stem distance
- 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
- Bivariate Markov chain embeddable variables of polynomial type
- String matching problems over free partially commutative monoids
- Cross-monotone subsequences
- On isomorphism classes of generalized Fibonacci cubes
- The Goulden—Jackson cluster method: extensions, applications and implementations
- Pattern correlation matrices and their properties
- On the fair coin tossing process
- How long does it take to see a flat Brownian path on the average?
- The Goulden-Jackson cluster method for cyclic words
- On the waiting time till each of some given patterns occurs as a run
- On cyclic strings avoiding a pattern
- Designing optimal- and fast-on-average pattern matching algorithms
- Gambling Teams and Waiting Times for Patterns in Two-State Markov Chains
- The intersite distances between pattern occurrences in strings generated by general discrete- and continuous-time models: an algorithmic approach
- Bijective proofs of some classical partition identities
- An analytical comparison of two string searching algorithms
- Where to place a hole to achieve a maximal escape rate
- The first return time test of pseudorandom numbers
- The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain
- A characterization of the words occurring as factors in a minimum number of words
- Periodicity and repetitions in parameterized strings
- Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata
- Oscillation properties of expected stopping times and stopping probabilities for patterns consisting of consecutive states in Markov chains
- Periodicity and Repetitions in Parameterized Strings
- Construction of voting situations concordant with ranking patterns
- Ranking graphs through hitting times of Markov chains
- A natural bijection for contiguous pattern avoidance in words
- Generalizations of the Goulden–Jackson cluster method
- Optimal pattern matching algorithms
- Entropy bounds for multi-word perturbations of subshifts
- From Hertzsprung's problem to pattern-rewriting systems
- Asymptotic bounds for the number of closed and privileged words
- Extension of Goulden–Jackson cluster method on pattern occurrences in random sequences and comparison with Régnier–Szpankowski method
- Statistical Properties of Factor Oracles
- 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
- Waiting times and stopping probabilities for patterns in Markov chains
- On the Perron root and eigenvectors of a non-negative integer matrix
- On expected waiting time until given words appear in random sequence
- Rarity and exponentiality: an extension of Keilson's theorem, with applications
- The Penney's game with group action
- SUBSHIFTS OF FINITE TYPE WITH A HOLE
- Computation of exact probabilities associated with overlapping pattern occurrences
- Content-based networks: A pedagogical overview
- Counting independent sets in Riordan graphs
- Pattern statistics and Vandermonde matrices.
- First Occurrence in Pairs of Long Words: A Penney-ante Conjecture of Pevzner
- Optimal Strategy for the First Player in the Penney Ante Game
- On the Perron root and eigenvectors associated with a subshift of finite type
- Patterns in random walks and Brownian motion
- Subsequence frequency in binary words
- The number of optimal strategies in the Penney-Ante game
- Calculating the numbers of representations and the Garsia entropy in linear numeration systems
- Permutations avoiding 1324 and patterns in Łukasiewicz paths
- Where and when orbits of chaotic systems prefer to go
- Stochastic precedence and minima among dependent variables
- Construction of aggregation paradoxes through load-sharing models
- Learning Temporal Structures of Random Patterns by Generating Functions
- Reconstructing strings from substrings (Extended abstract)
- Algebraic generating functions for languages avoiding Riordan patterns
- Formulas for the numbers of sequences containing a given pattern given number of times
- Analytic combinatorics of lattice paths with forbidden patterns: asymptotic aspects and Borges's theorem
- Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata
This page was built for publication: String overlaps, pattern matching, and nontransitive games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1149796)
