Relations on words
From MaRDI portal
Publication:505060
DOI10.1016/j.indag.2016.11.018zbMath1369.68272arXiv1602.03364OpenAlexW2271824796MaRDI QIDQ505060
Publication date: 18 January 2017
Published in: Indagationes Mathematicae. New Series (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1602.03364
periodicitypattern avoidancecombinatorics on words\(M\)-equivalenceParikh matricesabelian equivalence\(k\)-abelian equivalenceassociated relationscombinatorial coefficientscomplexity function of an infinite wordgrowth function of a languageuniform recurrence
Related Items
Fractional meanings of nonrepetitiveness, Order of weak \(M\)-relation and Parikh matrices, Binomial complexities and Parikh-collinear morphisms, On extended boundary sequences of morphic and Sturmian words, On the 2-binomial complexity of the generalized Thue-Morse words, Counting subwords in circular words and their Parikh matrices, Characterizations of families of morphisms and words via binomial complexities, Computing the \(k\)-binomial complexity of the Thue-Morse word, Templates for the \(k\)-binomial complexity of the Tribonacci word
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Generalized Pascal triangle for binomial coefficients of words
- On a generalization of abelian equivalence and complexity of infinite words
- Fixed points avoiding abelian \(k\)-powers
- On some generalizations of abelian power avoidability
- Another generalization of abelian equivalence: binomial complexity of infinite words
- On the 2-abelian complexity of the Thue-Morse word
- Polynomial versus exponential growth in repetition-free binary words
- Codes, orderings, and partial words
- Some unsolved problems
- Growth rate of binary words avoiding \(xxx^{R}\)
- Criteria for the matrix equivalence of words
- Balance and abelian complexity of the Tribonacci word
- Enumeration of irreducible binary words
- Strongly non-repetitive sequences and progression-free sets
- Subword complexities of various classes of deterministic developmental languages without interactions
- Descendants of primitive substitutions
- Partial words and a theorem of Fine and Wilf
- On the complexity of infinite sequences
- How many squares must a binary sequence contain?
- On a reconstruction problem for sequences
- A characterization of substitutive sequences using return words
- On the number of Abelian square-free words on four letters
- On nonrepetitive sequences
- Reconstruction from subsequences.
- Balances for fixed points of primitive substitutions.
- Periodicity on partial words
- Coding rotations on intervals
- Reconstructing words from subwords in linear time
- Uniformly growing k-th power-free homomorphisms
- Subword histories and Parikh matrices
- Extending Parikh matrices
- Abelian complexity and abelian co-decomposition
- The abelian complexity of the paperfolding word
- Subword balance, position indices and power sums
- A new approach to the 2-regularity of the \(\ell\)-abelian complexity of 2-automatic sequences
- Avoiding 2-binomial squares and cubes
- 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
- Strongly k-Abelian Repetitions
- Existence of an infinite ternary 64-abelian square-free word
- On the Complexity of the Equivalence Problem for Probabilistic Automata
- k-Abelian Pattern Matching
- Variations of the Morse-Hedlund Theorem for k-Abelian Equivalence
- Formal Languages, Automata and Numeration Systems 1
- AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY
- FINE AND WILF'S THEOREM FOR PARTIAL WORDS WITH ARBITRARILY MANY WEAK PERIODS
- Abelian complexity of minimal subshifts
- ON ABELIAN POWER-FREE MORPHISMS
- A sharpening of the Parikh mapping
- Avoiding Three Consecutive Blocks of the Same Size and Same Sum
- On Growth and Fluctuation of k-Abelian Complexity
- Complexité des facteurs des mots infinis engendrés par morphismes itérés
- On the definition of a family of automata
- Combinatorics, Words and Symbolic Dynamics
- 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
- On the periodicity of morphisms on free monoids
- Generalized Parikh mappings and homomorphisms
- A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
- Représentation géométrique de suites de complexité $2n+1$
- Combinatoire des codages de rotations
- Automatic Sequences
- Decidability of periodicity for infinite words
- Decidability of the HD0L ultimate periodicity problem
- Abelian squares are avoidable on 4 letters
- Abelian complexity function of the Tribonacci word
- Abelian periods, partial words, and an extension of a theorem of Fine and Wilf
- FINE AND WILF'S THEOREM FOR k-ABELIAN PERIODS
- On Context-Free Languages
- Is There a Sequence on Four Symbols in Which No Two Adjacent Segments are Permutations of One Another?
- Uniform tag sequences
- Sequences with minimal block growth
- Abelian returns in Sturmian words
- A characterization of Sturmian words by return words
- Partial words and a theorem of Fine and Wilf revisited