Publication:4529547
From MaRDI portal
zbMath1001.68093MaRDI QIDQ4529547
Publication date: 3 May 2002
68R15: Combinatorics on words
68-02: Research exposition (monographs, survey articles) pertaining to computer science
11B85: Automata sequences
Related Items
Factors of characteristic words of irrational numbers, Generalised fine and Wilf's theorem for arbitrary number of periods, Sturmian words and a criterium by Michaux-Villemaire, On a conjecture about finite fixed points of morphisms, The algebra of binary search trees, Rotation encoding and self-similarity phenomenon, Combinatorial properties of infinite words associated with cut-and-project sequences, Two-dimensional iterated morphisms and discrete planes, Lattices and multi-dimensional words, Canonical substitutions tilings of Ammann-Beenker type, Real numbers having ultimately periodic representations in abstract numeration systems, Crucial words and the complexity of some extremal problems for sets of prohibited words, Polynomial versus exponential growth in repetition-free binary words, Optimal broadcasting in the back to back d-ary trees, On the fragmentary complexity of symbolic sequences, Valuations of languages, with applications to fractal geometry, Generalized Witt formulae and comma-free codes, Efficient detection of quasiperiodicities in strings, On the anti-exceedance distribution on the symmetric group and its subgroups, Constructions of standard bases of right \(K\langle A\rangle\)- modules, On average sequence complexity, Linear-time computation of local periods, Border correlation of binary words, The factor composition matrix of sequences, Circular Sturmian words and Hopcroft's algorithm, Completing codes in a sofic shift, A decomposition of Solomon's descent algebra, Solutions principales et rang d'un système d'équations avec constantes dans le monoide libre, Locating factors of the infinite Fibonacci word, Combinatorial properties of smooth infinite words, Lyndon + Christoffel = digitally convex, Run-hierarchical structure of digital lines with irrational slopes in terms of continued fractions and the Gauss map, On \(q\)-analogs of weight multiplicities for the Lie superalgebras \(\mathfrak{gl}(n,m)\) and \(\mathfrak{spo}(2n,M)\), Relation between powers of factors and the recurrence function characterizing Sturmian words, Two equivalence relations on digital lines with irrational slopes. A continued fraction approach to upper mechanical words, On a generalization of Christoffel words: epichristoffel words, Square-free words as products of commutators., Denjoy systems and substitutions, Algebraic relations between harmonic sums and associated quantities., Optimal routing in two parallel queues with exponential service times, Palindromic prefixes and episturmian words, Continued fractions and numeration in the Fibonacci base, Nonrepetitive colorings of trees, Languages generated by iterated idempotency, Quasiperiodic Sturmian words and morphisms, Dejean's conjecture and Sturmian words, The origins of combinatorics on words, Zero-measure Cantor spectrum for Schrödinger operators with low-complexity potentials, On the combinatorics of crystal graphs. I: Lusztig's involution, On abelian 2-avoidable binary patterns, Pattern avoidance on graphs, On Sturmian graphs, Growth problems for avoidable words, Non-repetitive words relative to a rewriting system, A public key cryptosystem based on Lyndon words, On the action of the symmetric group on the free Lie algebra and the partition lattice, Two-pattern strings. II: Frequency of occurrence and substring complexity, Nonrepetitive colorings of graphs -- a survey, Matrices of 3-iet preserving morphisms, Maximal repetitions in strings, Substitutions on two letters, cutting segments and their projections, How many runs can a string contain?, On bases of identities for the \(\omega\)-variety generated by locally testable semigroups., Thue type problems for graphs, points, and numbers, \(\beta\)-expansions in algebraic function fields over finite fields, General theory of information transfer: Updated, Periodicity and repetitions in parameterized strings, Polynomial growth in semigroup varieties., Beta-expansions for infinite families of Pisot and Salem numbers, Subword histories and associated matrices, Rich, Sturmian, and trapezoidal words, Metric properties and exceptional sets of \(\beta \)-expansions over formal Laurent series, Sturmian morphisms, the braid group \(B_4\), Christoffel words and bases of \(F_2\), On self-matching within integer part sequences, Powers of rationals modulo 1 and rational base number systems, Palindromic richness, The complexity of nonrepetitive coloring, Infinite-vertex free profinite semigroupoids and symbolic dynamics., Testing avoidability on sets of partial words is hard, Burrows-Wheeler transform and Sturmian words, Infinite periodic points of endomorphisms over special confluent rewriting systems, Repetitions in beta-integers, On the dichotomy of Perron numbers and beta-conjugates, Sturmian substitutions on two letters, cutting paths and their projections, Cubic pisot unit combinatorial games, Boundary of central tiles associated with Pisot beta-numeration and purely periodic expansions, Intersecting periodic words, An application of the matrix representation of transductions, Une généralisation des théorèmes de Higman et de Simon aux mots infinis, A characterization of power-free morphisms, Some properties of commutation in free partially commutative monoids, The Church-Rosser property and special Thue systems, Square-free words on partially commutative free monoids, Sur la combinatoire des codes à deux mots. (On the combinatorics of two-word codes), Special monoids and special Thue systems, Sur une majoration du nombre de groupes définis par générateurs et ayant une seule relation. (An upper bound for the number of groups defined by generators and only one relator), On regular trace languages, Le calcul rapide des mélanges de deux mots. (Fast computing of the shuffle of two words), A formula for iterated derivatives along trajectories of nonlinear systems, Multidimensional unrepetitive configurations, Fast parallel Lyndon factorization with applications, On a characteristic property of ARNOUX–RAUZY sequences, A UNIQUE DECOMPOSITION THEOREM FOR FACTORIAL LANGUAGES, Episturmian morphisms and a Galois theorem on continued fractions, The structure of invertible substitutions on a three-letter alphabet, On multiplicatively dependent linear numeration systems, and periodic points, Density of Critical Factorizations, A Note on a Conjecture of Duval and Sturmian Words, On the distribution of characteristic parameters of words, Complexity of infinite words associated with beta-expansions, Episturmian words: a survey, Squares and cubes in Sturmian sequences, EQUATIONS IN FREE INVERSE MONOIDS, Substitutions par des motifs en dimension 1, On substitution invariant Sturmian words: an application of Rauzy fractals, Balance properties of the fixed point of the substitution associated to quadratic simple Pisot numbers, Combinatorial View of Digital Convexity, Continued Fractions and Digital Lines with Irrational Slopes, ω-powers and descriptive set theory, Double sequences of low complexity, Fractional powers in Sturmian words, Covering numbers: Arithmetics and dynamics for rotations and interval exchanges, Restricted permutations, Recurrence and periodicity in infinite words from local periods, Recognizing string graphs in NP, Unavoidable sets, On the min DSS problem of closed discrete curves, Nonrepetitive colorings of graphs, Endomorphisms of words in a quiver, Rich and Periodic-Like Words, On Negative Bases, Word Equations with One Unknown, Balanced Words Having Simple Burrows-Wheeler Transform, Prefixes of infinite words and ambiguous context-free languages, Avoidable patterns on two letters, On the generation of powers by OS schemes, Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée. (Generation of a section of conjugation classes and trees of Lyndon words of bounded length), Thue-Morse sequence and p-adic topology for the free monoid, On the conjugation of standard morphisms, Optimal canonization of all substrings of a string, Combinatorics of Hall trees and Hall words, A structure to decide reachability in Petri nets, On the rank of the subsets of a free monoid, Optimal parallel detection of squares in strings, Lyndon trees, Rationality of division orderings, Deciding whether a finite set of words has rank at most two, On two definitions of observation spaces, A bijective census of nonseparable planar maps, A complete equational axiomatization for MPA with string iteration, Commutativity in free inverse monoids, Periodicity and the golden ratio, Continuity in a pathwise sense with respect to the coefficients of solutions of stochastic differential equations, On repetition-free binary words of minimal density, Descent classes of permutations with a given number of fixed points, Scattered deletion and commutativity, Parallel RAM algorithms for factorizing words, Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach, Lyndon traces and shuffle algebras, Forbidden subsequences, The index of Sturmian sequences, Palindromes in the Fibonacci word, Over testable languages, Polynomial closure and unambiguous product, A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs, Euclidean strings, Periodicity, morphisms, and matrices., On the computational complexity of infinite words., Equations in free semigroups with involution and their relation to equations in free groups., Hierarchical structures in Sturmian dynamical systems, Ascending runs of sequences of geometrically distributed random variables: A probabilistic analysis, Some properties of the factors of Sturmian sequences., Invertible substitutions and Sturmian sequences., Combinatorics of periods in strings., Words whose complexity satisfies lim \(\frac{p(n)}{n} = 1\)., On the independence of equations in three variables., Lyndon factorization of the Prouhet words., Fine and Wilf words for any periods, Imbalances in Arnoux-Rauzy sequences, Repetitiveness of languages generated by morphisms, Enumeration of planar constellations, Episturmian words and episturmian morphisms, A combinatorial problem on trapezoidal words., Words and forbidden factors, Some results on \(k\)-power-free morphisms, Balance properties of multi-dimensional words, Transcendence of Sturmian or morphic continued fractions, Explicit test sets for iterated morphisms in free monoids and metabelian groups, An extension of the periodicity lemma to longer periods, The standard factorization of Lyndon words: an average point of view, Patterns in words and languages, Dynamical upper bounds for one-dimensional quasicrystals, A note on the Burrows-Wheeler transformation, Partial words and the critical factorization theorem, A combinatorial approach to jumping particles, Action of the symmetric group on sets of skew-tableaux with prescribed matrix realization, Binomial coefficients and anti-exceedances of even permutations: A combinatorial proof, Morphismes unispectraux. (Unispectral morphisms), Comment on a remark of Forys, Sturmian words and the permutation that orders fractional parts, Two-pattern strings. I: A recognition algorithm, Digital straightness -- a review, An optimal test on finite unavoidable sets of words, Hierarchie et fermeture de certaines classes de tag-systèmes, An analogue of the plactic monoid for binary search trees, Conway's problem for three-word sets., Palindrome complexity., Semiperiodic words and root-conjugacy., On Fine and Wilf's theorem for bidimensional words., On some generalizations of the Thue-Morse morphism., Unavoidable sets of words of uniform length, Periodicity vectors for labelled trees, Invertible substitutions on a three-letter alphabet., Powers in Sturmian sequences, On a conjecture on bidimensional words., Many aspects of defect theorems, Uniform words, The structure of invertible substitutions on a three-letter alphabet, \(m\)-balanced words: A generalization of balanced words, Characterisations of balanced words via orderings, Sturmian words, \(\beta\)-shifts, and transcendence, Overlap-free morphisms and finite test-sets, Scaling properties of generalized Carlitz sequences of polynomials, Eulerian calculus. II: An extension of Han's fundamental transformation, Lyndon heaps: An analogue of Lyndon words in free partially commutative monoids, Some combinatorial properties of infinite words and applications to semigroup theory, Combinatorics of geometrically distributed random variables: Left-to-right maxima, Palindromes and Sturmian words, Calcul de longueurs de chaînes de réécriture dans le monoïde libre, Periodicity, repetitions, and orbits of an automatic sequence, A Sturmian sequence related to the uniqueness conjecture for Markoff numbers, On systems of word equations over three unknowns with at most six occurrences of one of the unknowns, Simple equations on binary factorial languages, Pattern avoidance by palindromes, Burrows-Wheeler transform and palindromic richness, Fine and Wilf words for any periods. II, Orthogonal projection onto the free Lie algebra, Some properties of the Tribonacci sequence, Dynamical directions in numeration, Palindromic complexity of infinite words associated with simple Parry numbers, Fractal representation of the attractive lamination of an automorphism of the free group., Substitutions, abstract number systems and the space filling property, Diffraction spectra of weighted Delone sets on beta-lattices with beta a quadratic unitary Pisot number, On the complexity of infinite words generated by countable \(q\)-automata, Substitutions with cofinal fixed points, On gaps in Rényi \(\beta\)-expansions of unity for \(\beta>1\) an algebraic number, Reversals and palindromes in continued fractions, On alpha-adic expansions in Pisot bases, Functional stepped surfaces, flips, and generalized substitutions, 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, Algorithms for subsequence combinatorics, A palindromization map for the free group, Quasiperiodic and Lyndon episturmian words, Exponential lower bounds for the number of words of uniform length avoiding a pattern, The number of runs in a string, Existence of finite test-sets for \(k\)-power-freeness of uniform morphisms, The equality problem for infinite words generated by primitive morphisms, On Dejean's conjecture over large alphabets, Languages with mismatches, Partial words and the critical factorization theorem revisited, From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization, An extension of the Burrows-Wheeler transform, On a class of infinite words with affine factor complexity, Syntactical and automatic properties of sets of polynomials over finite fields, Codimensions of algebras and growth functions, Symmetrized \(\beta \)-integers, Right coideal subalgebras in \(U_q(\mathfrak{sl}_{n+1})\), Subword complexity and projection bodies, Breaking the rhythm on graphs, A new combinatorial approach to sequence comparison, A basis for the right quantum algebra and the ``\(1= q\) principle, On different generalizations of episturmian words, Words derivated from Sturmian words, Commutation with codes, Fractional parts of powers and Sturmian words, Binary number systems for \(\mathbb Z^{k}\), Sequential?, Centers in domains with quadratic growth., Substitution dynamical systems: characterization of linear repetitivity and applications, Language structure of pattern Sturmian words, Averages of automatic sequences, Periods in extensions of words, The descent statistic on involutions is not log-concave, The alternating greedy expansion and applications to computing digit expansions from left-to-right in cryptography, Inequalities characterizing standard Sturmian and episturmian words, Smooth words over arbitrary alphabets, Arithmetic Meyer sets and finite automata, A simple proof that a word of length \(n\) has at most \(2n\) distinct squares, Hardness results for the center and median string problems under the weighted and unweighted edit distances, The non-parametrizability of the word equation \(xyz=zvx\): a short proof, A generalization of repetition threshold, A characterization of periodicity of bi-infinite words, A multidimensional critical factorization theorem, Rauzy substitutions and multi-dimensional Sturmian words, Braided version of Shirshov-Witt theorem, A SURVEY ON ALGORITHMIC ASPECTS OF TANDEM REPEATS EVOLUTION, A test-set fork-power-free binary morphisms, Aperiodicity Measure for Infinite Sequences, A generator of morphisms for infinite words, Optimization and majorization of invariant measures, On univoque Pisot numbers, Periodicity and Repetitions in Parameterized Strings, Defect theorem in the plane, Combinatoire de mots récurrents de complexitén+2, Deciding Innermost Loops, Sturmian and Episturmian Words, Some Algebraic Properties of Machine Poset of Infinite Words, From Bi-ideals to Periodicity, Musical intervals and special linear transformations, The first return time properties of an irrational rotation, Well Quasi-orders in Formal Language Theory, The Average State Complexity of the Star of a Finite Set of Words Is Linear, On a Generalization of Standard Episturmian Morphisms, Relationally Periodic Sequences and Subword Complexity, An Analysis and a Reproof of Hmelevskii’s Theorem, Balance Properties and Distribution of Squares in Circular Words, A note on univoque self-Sturmian numbers, Study of irreducible balanced pairs for substitutive languages, On extremal properties of the Fibonacci word, Look and Say Fibonacci, Counting Ordered Patterns in Words Generated by Morphisms, How Many Figure Sets Are Codes?, Equations on partial words, On Critical exponents in fixed points ofk-uniform binary morphisms, Least Periods of Factors of Infinite Words, A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems, Crystal bases and combinatorics of infinite rank quantum groups, Constructing Infinite Words of Intermediate Arithmetical Complexity, Directive words of episturmian words: equivalences and normalization, ON INTEGER SEQUENCES GENERATED BY LINEAR MAPS, On the Complexity of Deciding Avoidability of Sets of Partial Words
