scientific article; zbMATH DE number 2183071

Publication date: 27 June 2005

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

words automata DNA sequences Markov models pattern matching number theory tries biomathematics algorithms on words natural languages

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics on words (68R15) Formal languages and automata (68Q45) Protein sequences, DNA sequences (92D20) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Data structures (68P05) Natural language processing (68T50) Automata sequences (11B85)

Related Items

Fractional meanings of nonrepetitiveness, On the \(t\)-adic Littlewood conjecture, On del-robust primitive words, Indeterminate string factorizations and degenerate text transformations, Characterization of dense patterns having distinct squares, Morphic sequences versus automatic sequences, Lyndon + Christoffel = digitally convex, Dynamical directions in numeration, Fractal representation of the attractive lamination of an automorphism of the free group., Substitutions with cofinal fixed points, Discrete rotations and symbolic dynamics, A note on the number of squares in a word, Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words, On left and right seeds of a string, On the approximation ratio of LZ-end to LZ77, Existence of finite test-sets for \(k\)-power-freeness of uniform morphisms, Cut norm discontinuity of triangular truncation of graphons, Succinct 2D dictionary matching, Gray codes for Fibonacci \(q\)-decreasing words, Quasiperiodic Sturmian words and morphisms, The origins of combinatorics on words, Waiting times for clumps of patterns and for structured motifs in random sequences, Border correlations, lattices, and the subgraph component polynomial, Computing primitively-rooted squares and runs in partial words, Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source, Efficient seed computation revisited, Clustering genomic words in human DNA using peaks and trends of distributions, Enhanced string covering, Suffix array and Lyndon factorization of a text, On generalized Lyndon words, Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. II: Reconstruction with forbidden words, On shuffled-square-free words, Calculating the numbers of representations and the Garsia entropy in linear numeration systems, A note on Sturmian words, The identity problem of finitely generated bi-ideals, Average case analysis of Moore's state minimization algorithm, Period recovery of strings over the Hamming and edit distances, A split-based incremental deterministic automata minimization algorithm, Compound patterns and generating functions: from basic waiting times to counts of occurrence, A linear time and space algorithm for detecting path intersection in \(\mathbb Z^d\), On recognising words that are squares for the shuffle product, On the average number of regularities in a word, On the shortest distance between orbits and the longest common substring problem, Textual data compression in computational biology: algorithmic techniques, Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. I. Reconstruction without forbidden words, On the minimal alphabet size in multidimensional unrepetitive configurations, Maximal repetitions in strings, Languages with mismatches, \(k\)-abelian pattern matching, Indeterminate strings, prefix arrays \& undirected graphs, Another generalization of abelian equivalence: binomial complexity of infinite words, Average number of occurrences of repetitions in a necklace, Computing the number of cubic runs in standard Sturmian words, Enumeration and generation with a string automata representation, From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization, Distributions associated with general runs and patterns in hidden Markov models, Generalized pattern matching and periodicity under substring consistent equivalence relations, 2D Lyndon words and applications, Efficient on-line repetition detection, Some variations on a theme of Irina Mel'nichuk concerning the avoidability of patterns in strings of symbols, On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties, Where to place a hole to achieve a maximal escape rate, On different generalizations of episturmian words, On the maximum number of cubic subwords in a word, Growth of repetition-free words -- a review, Bifix codes and interval exchanges, An extension of Christoffel duality to a subset of Sturm numbers and their characteristic words, The expected profile of digital search trees, The perimeter of words, Some characterizations of finite Sturmian words., Non-uniform random generation of generalized Motzkin paths, Characteristic morphisms of generalized episturmian words, The index of a binary word, Balance and abelian complexity of the Tribonacci word, Reactive automata, Optimality of some algorithms to detect quasiperiodicities, On z-factorization and c-factorization of standard episturmian words, An efficient generalized shift-rule for the prefer-max de Bruijn sequence, Grasshopper avoidance of patterns, Periods in extensions of words, Moments of the count of a regular expression in a heterogeneous random sequence, Counting and generating permutations in regular classes, Recognizing binary shuffle squares is \textsf{NP}-hard, Inverse Lyndon words and inverse Lyndon factorizations of words, On the tiling by translation problem, Wasserstein and Kolmogorov error bounds for variance-gamma approximation via Stein's method. I, The alternating BWT: an algorithmic perspective, Longest property-preserved common factor: a new string-processing framework, Gray code orders for \(q\)-ary words avoiding a given factor, Fully-online suffix tree and directed acyclic word graph construction for multiple texts, Average complexity of Moore's and Hopcroft's algorithms, On primary and secondary repetitions in words, Two linear-time algorithms for computing the minimum length polygon of a digital contour, Repetitions in strings: algorithms and combinatorics, The operator approach to entropy games, Perspectives: Journal of Discrete Algorithms Special StringMasters Issue (2015), On a generalization of Thue sequences, A maximal entropy stochastic process for a timed automaton, State complexity of prefix distance, Segmental partially ordered generalized patterns, On the size of transducers for bidirectional decoding of prefix codes, Unnamed Item, Hidden automatic sequences, On digital blocks of polynomial values and extractions in the Rudin–Shapiro sequence, Episturmian words: a survey, Decidability Problems for Self-induced Systems Generated by a Substitution, State Complexity of Prefix Distance, Random graph languages, Constructing Words with High Distinct Square Densities, The palindromization map, The square density of words having a sequence of FS-double squares, Quadratic characters with positive partial sums, Finding the cyclic covers of a string, Construction of general forms of ordinary generating functions for more families of numbers and multiple variables polynomials, Abelian combinatorics on words: a survey, Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics, Formulae and Asymptotics for Coefficients of Algebraic Functions, Fast circular dictionary-matching algorithm, Sturmian and Episturmian Words, General Framework, Unnamed Item, The Average State Complexity of the Star of a Finite Set of Words Is Linear, On a Generalization of Standard Episturmian Morphisms, Bounds on Powers in Strings, A characterization of words of linear complexity, Equations on partial words, Periodic codings of Bratteli-Vershik systems, A uniform cube-free morphism isk-power-free for all integersk≥ 4, Searching and Indexing Circular Patterns, Efficient Seeds Computation Revisited, Substitutions par des motifs en dimension 1, Descriptional Complexity of Error Detection, Equations enforcing repetitions under permutations, Indexing Circular Patterns, On the First k Moments of the Random Count of a Pattern in a Multistate Sequence Generated by a Markov Source, Nonrepetitive and pattern-free colorings of the plane, State Complexity of Suffix Distance, Music and combinatorics on words: a historical survey, Combinatorial View of Digital Convexity, Unnamed Item, Circular pattern matching with \(k\) mismatches, Locally catenative sequences and Turtle graphics, Moderate Deviations for Word Counts in Biological Sequences, Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour, A Linear Time and Space Algorithm for Detecting Path Intersection, Distribution of Clump Statistics for a Collection of Words, Some Applications of the Schutzenberger-Bertoni Method, Improved compound Poisson approximation for the number of occurrences of any rare word family in a stationary markov chain