Relations on words
From MaRDI portal
Publication:505060
DOI10.1016/J.INDAG.2016.11.018zbMATH Open1369.68272arXiv1602.03364OpenAlexW2271824796MaRDI QIDQ505060FDOQ505060
Authors: Michel Rigo 
Publication date: 18 January 2017
Published in: Indagationes Mathematicae. New Series (Search for Journal in Brave)
Abstract: In the first part of this survey, we present classical notions arising in combinatorics on words: growth function of a language, complexity function of an infinite word, pattern avoidance, periodicity and uniform recurrence. Our presentation tries to set up a unified framework with respect to a given binary relation. In the second part, we mainly focus on abelian equivalence, -abelian equivalence, combinatorial coefficients and associated relations, Parikh matrices and -equivalence. In particular, some new refinements of abelian equivalence are introduced.
Full work available at URL: https://arxiv.org/abs/1602.03364
Recommendations
combinatorics on wordspattern avoidance\(M\)-equivalenceParikh matricesperiodicityabelian equivalence\(k\)-abelian equivalenceassociated relationscombinatorial coefficientscomplexity function of an infinite wordgrowth function of a languageuniform recurrence
Cites Work
- How many squares must a binary sequence contain?
- Title not available (Why is that?)
- Title not available (Why is that?)
- Growth rate of binary words avoiding \(xxx^{R}\)
- A characterization of substitutive sequences using return words
- A sharpening of the Parikh mapping
- Automatic Sequences
- On Context-Free Languages
- Uniform tag sequences
- Criteria for the matrix equivalence of words
- Subword histories and Parikh matrices
- Formal Languages, Automata and Numeration Systems 1
- Title not available (Why is that?)
- Decidability of the HD0L ultimate periodicity problem
- Uniformly growing k-th power-free homomorphisms
- Noncommutative rational series with applications
- Représentation géométrique de suites de complexité $2n+1$
- Balance and abelian complexity of the Tribonacci word
- AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY
- Abelian complexity of minimal subshifts
- On the definition of a family of automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Abelian returns in Sturmian words
- Some unsolved problems
- Generalized Pascal triangle for binomial coefficients of words
- Strongly non-repetitive sequences and progression-free sets
- Title not available (Why is that?)
- Abelian squares are avoidable on 4 letters
- Subword complexities of various classes of deterministic developmental languages without interactions
- On the complexity of infinite sequences
- Complexité des facteurs des mots infinis engendrés par morphismes itérés
- Avoiding three consecutive blocks of the same size and same sum
- On some generalizations of abelian power avoidability
- Extending Parikh matrices
- Sequences with minimal block growth
- Variations of the Morse-Hedlund theorem for \(k\)-abelian equivalence
- Combinatorics, Words and Symbolic Dynamics
- On the periodicity of morphisms on free monoids
- Generalized Parikh mappings and homomorphisms
- Decidability of periodicity for infinite words
- Partial words and a theorem of Fine and Wilf
- On a reconstruction problem for sequences
- Reconstruction from subsequences.
- Existence of an infinite ternary 64-abelian square-free word
- On a generalization of abelian equivalence and complexity of infinite words
- A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
- Title not available (Why is that?)
- Abelian periods, partial words, and an extension of a theorem of Fine and Wilf
- A characterization of Sturmian words by return words
- On nonrepetitive sequences
- Title not available (Why is that?)
- Polynomial versus exponential growth in repetition-free binary words
- Title not available (Why is that?)
- Fixed points avoiding abelian \(k\)-powers
- Fine and Wilf's theorem for partial words with arbitrarily many weak periods
- Partial words and a theorem of Fine and Wilf revisited
- Subword balance, position indices and power sums
- Periodicity on partial words
- Reconstructing words from subwords in linear time
- Enumeration of irreducible binary words
- Balances for fixed points of primitive substitutions.
- Abelian complexity and abelian co-decomposition
- The abelian complexity of the paperfolding word
- On the number of Abelian square-free words on four letters
- Avoiding 2-binomial squares and cubes
- k-Abelian Pattern Matching
- ON ABELIAN POWER-FREE MORPHISMS
- Another generalization of abelian equivalence: binomial complexity of infinite words
- On unavoidability of \(k\)-abelian squares in pure morphic words
- Descendants of primitive substitutions
- Coding rotations on intervals
- A new approach to the 2-regularity of the \(\ell\)-abelian complexity of 2-automatic sequences
- A note on abelian returns in rotation words
- Relational codes of words
- Connections between subwords and certain matrix mappings
- On the index of Simon's congruence for piecewise testability
- Characterization of a word by its subwords
- Strongly \(k\)-abelian repetitions
- On the Complexity of the Equivalence Problem for Probabilistic Automata
- On growth and fluctuation of \(k\)-abelian complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Compatibility relations on codes and free monoids
- AVOIDING APPROXIMATE SQUARES
- On the periodicity of morphic words
- The theorem of Fine and Wilf for relational periods
- Combinatoire des codages de rotations
- On the 2-abelian complexity of the Thue-Morse word
- Abelian complexity function of the Tribonacci word
- Abelian complexity of fixed point of morphism \(0 \mapsto 012, 1 \mapsto 02, 2 \mapsto 1\)
- Fine and Wilf's theorem for \(k\)-abelian periods
- Is There a Sequence on Four Symbols in Which No Two Adjacent Segments are Permutations of One Another?
- Codes, orderings, and partial words
Cited In (17)
- Templates for the \(k\)-binomial complexity of the Tribonacci word
- Abelian properties of words
- Title not available (Why is that?)
- Fractional meanings of nonrepetitiveness
- Computing the \(k\)-binomial complexity of the Thue-Morse word
- Similarity relations and repetition-freeness
- Counting subwords in circular words and their Parikh matrices
- Order of weak \(M\)-relation and Parikh matrices
- Binomial complexities and Parikh-collinear morphisms
- An equivalence relation on a set of words of finite length
- Equivalence relations defined by numbers of occurrences of factors
- Similarity relations on words
- Characterizations of families of morphisms and words via binomial complexities
- On extended boundary sequences of morphic and Sturmian words
- On the 2-binomial complexity of the generalized Thue-Morse words
- Semantic relatedness
- Abelian combinatorics on words: a survey
This page was built for publication: Relations on words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q505060)
