The origins of combinatorics on words

DOI10.1016/J.EJC.2005.07.019zbMATH Open1111.68092OpenAlexW2049646746WikidataQ55951859 ScholiaQ55951859MaRDI QIDQ872058FDOQ872058

Jean Berstel, Dominique Perrin

Publication date: 27 March 2007

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2005.07.019

Mathematics Subject Classification ID

History of mathematics in the 18th century (01A50) History of mathematics in the 20th century (01A60) History of computer science (68-03) Combinatorics on words (68R15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Avoidable patterns in strings of symbols
• Subshifts of finite type and sofic systems
• A problem of arrangements
• BLOCKING SETS OF TERMS
• Poincaré recurrence and number theory
• An Introduction to Symbolic Dynamics and Coding
• Differentiable dynamical systems
• Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions
• Automatic Sequences
• Functional Composition Patterns and Power Series Reversion
• Uniform tag sequences
• On sets of integers containing k elements in arithmetic progression
• A variant of a recursively unsolvable problem
• A forbidden substructure characterization of Gauss codes
• On Burnside's Problem
• Normal Recurring Decimals
• Free differential calculus. IV: The quotient groups of the lower central series
• Substitutions in dynamics, arithmetics and combinatorics
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Fast Pattern Matching in Strings
• Uniqueness Theorems for Periodic Functions
• Recursive Unsolvability of a problem of Thue
• The Gauss Realizability Problem
• On Some Sequences of Integers
• Symbolic Dynamics II. Sturmian Trajectories
• A practical method for enumerating cosets of a finite abstract group
• Recursive unsolvability of group theoretic problems
• Concatenation as a basis for arithmetic
• On lacets and their manifolds
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
• Symbolic Dynamics
• A new proof of the Gauss interlace conjecture
• On a Factorisation of Free Monoids
• Classification of noncounting events
• Note on a Paper By I. J. Good
• Oriented subtrees of an arc digraph
• Treue Darstellung Liescher Ringe.
• Equations in free semigroups
• On the Number of Generators of a Free Product
• Triality and Lie algebras of type \(D_4\)
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Tarski’s problem about the elementary theory of free groups has a positive solution
• Free subalgebras of free associative algebras
• Wie der Beweis der Vermutung von Baudet gefunden wurde
• Exact Markov Probabilities from Oriented Linear Graphs
• On Subsemigroups of Free Semigroups
• A Characterization of the Double Point Structure of the Projection of a Polygonal Knot in Regular Position
• Finite combinatory processes—formulation

Cited In (81)

• Rate of convergence in the disjunctive chaos game algorithm
• An improvement of Prouhet’s 1851 result on multigrade chains
• Music and combinatorics on words: a historical survey
• On extremal factors of de Bruijn-like graphs
• A tight upper bound on the length of maximal bordered box repetition-free words
• Extensions and reductions of squarefree words
• Combinatorial approach of unified Apostol-type polynomials using \(\alpha \)-distanced words
• Numeric Lyndon-based feature embedding of sequencing reads for machine learning approaches
• No extremal square-free words over large alphabets
• Identities and derivative formulas for the combinatorial and Apostol-Euler type numbers by their generating functions
• On non-repetitive sequences of arithmetic progressions: the cases \(k\in\{4,5,6,7,8\}\)
• Random graph languages
• GROUP EXTENSIONS OVER INFINITE WORDS
• Title not available (Why is that?)
• Title not available (Why is that?)
• Subexponential estimates in the height theorem and estimates on numbers of periodic parts of small periods.
• Gröbner–Shirshov bases and their calculation
• Title not available (Why is that?)
• Repetitions in Toeplitz words and the Thue threshold
• Morphic sequences versus automatic sequences
• A periodicity theorem for acylindrically hyperbolic groups
• How to play Thue games
• Embedding subshifts of finite type into the Fibonacci–Dyck shift
• Normal Numbers and Computer Science
• An extension of Christoffel duality to a subset of Sturm numbers and their characteristic words
• A method for constructing artificial DNA libraries based on generalized de Bruijn sequences
• On interpolation functions for the number of \(k\)-ary Lyndon words associated with the Apostol-Euler numbers and their applications
• Asymptotic behavior of some factorizations of random words
• Decidability Problems for Self-induced Systems Generated by a Substitution
• Fractional meanings of nonrepetitiveness
• On Boolean automata isolated cycles and tangential double-cycles dynamics
• ENUMERATING NECKLACES WITH TRANSITIONS
• Nyldon words
• Grasshopper avoidance of patterns
• Perfect necklaces
• Analysis of generating functions for special words and numbers and algorithms for computation
• Symbol ratio minimax sequences in the lexicographic order
• Identities for Dirichlet and Lambert-type series arising from the numbers of a certain special word
• Cyclotomic factors of necklace polynomials
• Nonrepetitive list colorings of the integers
• N-WAY COMPOSITION OF WEIGHTED FINITE-STATE TRANSDUCERS
• New algebraic and geometric constructs arising from Fibonacci numbers.
• Completely uniformly distributed sequences based on de Bruijn sequences
• Word-Representable Graphs: a Survey
• Gray codes for Fibonacci \(q\)-decreasing words
• POWER SUMS ASSOCIATED WITH CERTAIN RECURSIVE PROCEDURES ON WORDS
• On extending de Bruijn sequences
• Subword balance, position indices and power sums
• Random iteration for infinite nonexpansive iterated function systems
• Three research directions in non-uniform cellular automata
• Generalizations of Parikh mappings
• Forbidden words in symbolic dynamics
• Can we replace reads by numeric signatures? Lyndon fingerprints as representations of sequencing reads for machine learning
• Computing generalized de Bruijn sequences
• Extremal overlap-free and extremal \(\beta\)-free binary words
• Algebraic properties of Parikh matrices of binary picture arrays
• The coolest way to generate binary strings
• On a generalization of Thue sequences
• On avoding \(r\)-repetitions in \(\mathbb R^2\)
• Piecewise periodicity structure estimates in Shirshov's height theorem.
• Avoiding 5/4-powers on the alphabet of nonnegative integers
• Extremal square-free words
• Nonrepetitive colorings of line arrangements
• Avoiding Multiple Repetitions in Euclidean Spaces
• \(k\)-ary Lyndon words and necklaces arising as rational arguments of Hurwitz-Lerch zeta function and Apostol-Bernoulli polynomials
• Computation of k-ary Lyndon words using generating functions and their differential equations
• Extending de Bruijn sequences to larger alphabets
• Applications of Apostol-type numbers and polynomials: approach to techniques of computation algorithms in approximation and interpolation functions
• Additive splitting methods for parallel solutions of evolution problems
• Multiplicity of positive periodic solutions in the superlinear indefinite case via coincidence degree
• Nonrepetitive and pattern-free colorings of the plane
• Lengths of extremal square-free ternary words.
• Solutions to the multi-dimensional Prouhet-Tarry-Escott problem resulting from composition of balanced morphisms
• Tower-type bounds for unavoidable patterns in words
• On the number of necklaces whose co-periods divide a given integer
• Positive subharmonic solutions to superlinear ODEs with indefinite weight
• On Prouhet's solution to the equal powers problem
• Inverse Lyndon words and inverse Lyndon factorizations of words
• BPS counting for knots and combinatorics on words
• Numerical evaluation of special power series including the numbers of Lyndon words: an approach to interpolation functions for Apostol-type numbers and polynomials
• Square-free extensions of words

   Recommendations

• Combinatorics on Words 👍 👎
• Title not available (Why is that?) 👍 👎
• Mini-workshop: Combinatorics on words. Abstracts from the mini-workshop held August 22nd -- August 28th, 2010. 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: The origins of combinatorics on words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q872058)