scientific article
From MaRDI portal
Publication:3659988
zbMath0514.20045MaRDI QIDQ3659988
Publication date: 1983
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
automatafree semigroupsnilpotent groupsLie algebrasfree groupsalgebras with polynomial identitiesfree algebrasformal languagescombinatorics on wordsasymptotic properties of words
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Combinatorics on words (68R15) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Combinatorial codes (94B25) Thue and Post systems, etc. (03D03) Research exposition (monographs, survey articles) pertaining to group theory (20-02)
Related Items
Some decision problems concerning semilinearity and commutation., Directed graphs and combinatorial properties of semigroups, Non-repetitive colorings of infinite sets, On a conjecture on bidimensional words., On maximal suffixes and constant-space linear-time versions of KMP algorithm., Lie idempotent algebras., Subword histories and Parikh matrices, Many aspects of defect theorems, Conjugates of characteristic Sturmian words generated by morphisms, Local periods and binary partial words: an algorithm, Extending Parikh matrices, Moments of conjugacy classes of binary words, Overlap-free morphisms and finite test-sets, Systems of word equations, polynomials and linear algebra: a new approach, On word equations originated from discrete dynamical systems related to antisymmetric cubic maps with some applications, BPS operators in \( \mathcal{N}=4 \) SO(\(N\)) super Yang-Mills theory: plethysms, dominoes and words, The join of the pseudovarieties of idempotent semigroups and locally trivial semigroups, BPS counting for knots and combinatorics on words, A bijective proof of a Touchard-Riordan formula, Trace maps as 3D reversible dynamical systems with an invariant, A basis for iterated stochastic integrals, Finding all periods and initial palindromes of a string in parallel, The word problem for nilpotent inverse monoids, A first step in characterizing three-element codes, Non-repetitive words: Ages and essences, On the Burnside problem for semigroups of matrices in the \((\max,+)\) algebra, A remarkable \(q,t\)-Catalan sequence and \(q\)-Lagrange inversion, The combinatorics of transition matrices between the bases of the symmetric functions and the \(B_ n\) analogues, Łukasiewicz language and diagonals of formal series, Graphical major indices, String cadences, Growth of power-free languages over large alphabets, Searching of gapped repeats and subrepetitions in a word, A generalized Bartholdi zeta function for a regular covering of a bipartite graph, The monoid of queue actions, On the number of gapped repeats with arbitrary gap, On the system of word equations \(x_{0} u^{i}_{1} x_{1} u^{i}_{2} x_{2} u^{i}_{3} x_{3}=y_{0} v^{i}_{1} y_{1} v^{i}_{2} y_{2} v^{i}_{3} y_{3}\) \((i=0,1,2,\ldots)\) in a free monoid, Lyndon factorization of the Prouhet words., Derivatives of rational expressions and related theorems., Inclines and incline matrices: A survey., Arithmetical complexity of symmetric D0L words., Enumeration of Łukasiewicz paths modulo some patterns, Fine and Wilf words for any periods, Periods and binary words, On shuffle products, acyclic automata and piecewise-testable languages, Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups, On square-free arithmetic progressions in infinite words, Fibonacci words in hyperbolic Pascal triangles, The maximal number of cubic runs in a word, On twin and anti-twin words in the support of the free Lie algebra, Local temporal logic is expressively complete for cograph dependence alphabets, On the equation \(x^k=z_1^{k_1}z_2^{k_2}\cdots z_n^{k_n}\) in a free semigroup, Random generation of DFAs, The standard factorization of Lyndon words: an average point of view, Partial words and the critical factorization theorem, Pattern statistics in faro words and permutations, Nonrepetitive list colorings of the integers, Lyndon word decompositions and pseudo orbits on \(q\)-nary graphs, Weighting by iteration: iterations of \(n\) variables means based on subdivisions of the standard \((n-1)\)-simplex, Variations on twins in permutations, Imaginary vectors in the dual canonical basis of \(U_q({\mathfrak n})\), On the factors of the Thue-Morse word on three symbols, The lattices of prefixes and overlaps of traces, Transducers and repetitions, Maximal prefix products, Anti-commutative languages and n-codes, Infinite words with linear subword complexity, Enumeration of factors in the Thue-Morse word, Factorizations of infinite sequences in semigroups, Lyndon-like and V-order factorizations of strings, Harmonic and gold Sturmian words, Approximating the Euclidean distance using non-periodic neighbourhood sequences, On the solutions of the universal differential equation with three regular singularities (on solutions of \(KZ_3)\), Sturmian words and words with a critical exponent, On lengths of words in context-free languages, Parametrisation of solutions of parametric equation in free monoid, Right and left locally testable languages, Riffle shuffles, cycles, and descents, Forbidden words in symbolic dynamics, A combinatorial property of the factor poset of a word, Conway's problem for three-word sets., Model checking of systems with many identical timed processes, Cumulative defect., A defect theorem for bi-infinite words., On some generalizations of the Thue-Morse morphism., Unavoidable sets of words of uniform length, Weighted zeta functions of digraphs, Unambiguous injective morphisms in free groups, Invertible substitutions and local isomorphisms, Repetitions in Toeplitz words and the Thue threshold, Basic analytic combinatorics of directed lattice paths, A combinatorial problem on trapezoidal words., Shuffle factorization is unique, The commutation of finite sets: A challenging problem, Multiple factorizations of words and defect effect, Lyndon words and shuffle algebras for generating the coloured multiple zeta values relations tables, On the support of graph Lie algebras, Locally periodic versus globally periodic infinite words, A solution to the problem of (\(A\),\(B\))-invariance for series, Simultaneous approximation to a real number and its square, On some factorizations of infinite words by elements of codes, Some permutations on Dyck words, Conjugacy relations of prefix codes, Primitive morphisms, On the facial Thue choice number of plane graphs via entropy compression method, Markov word patterns and a relation on \(\alpha\)-words, Semigroup theory of symmetry, Closure properties of pattern languages, Periodicity in rectangular arrays, Piecewise periodicity structure estimates in Shirshov's height theorem., A periodicity result of partial words with one hole, Crucial words and the complexity of some extremal problems for sets of prohibited words, Polynomial versus exponential growth in repetition-free binary words, Fixed points of endomorphisms over special confluent rewriting systems., A characterization of (regular) circular languages generated by monotone complete splicing systems, Some combinatorial properties of words in discrete dynamical systems from antisymmetric cubic maps, Eulerian quasisymmetric functions, On the least number of palindromes contained in an infinite word, A note on prefix primitive words, Introducing privileged words: privileged complexity of Sturmian words, Extracting powers and periods in a word from its runs structure, Simple real-time constant-space string matching, Infinite ternary square-free words concatenated from permutations of a single word, Ideals for character Hopf algebras., Artin-Schelter regular algebras of dimension five with two generators., Deterministic geoleader election in disoriented anonymous systems, Han's bijection via permutation codes, Extensions of rich words, Square-free words with square-free self-shuffles, Permuting operations on strings and their relation to prime numbers, Thue choosability of trees, On vectorizations of unary generalized quantifiers, Fixed points avoiding abelian \(k\)-powers, Eulerian quasisymmetric functions for the type B Coxeter group and other wreath product groups, On fragments of words, Selfdual substitutions in dimension one, Lexicographically least words in the orbit closure of the Rudin-Shapiro word, A new Euler-Mahonian constructive bijection, On the maximal sum of exponents of runs in a string, A linear algorithm for string reconstruction in the reverse complement equivalence model, Palindromic complexity of codings of rotations, Growth properties of power-free languages, Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. I. Reconstruction without forbidden words, The Ehrenfeucht-Silberger problem, Periodicity forcing words, How the character comparison order shapes the shift function of on-line pattern matching algorithms, A shrinking lemma for indexed languages, On some decision problems for trace codings, On a combinatorial property of Sturmian words, A division property of the Fibonacci word, Dynamical properties of PWD0L systems, Palindromic sequences generated from marked morphisms, Nonrepetitive colorings of line arrangements, A new solution for Thue's problem, The sequence of return words of the Fibonacci sequence, Transfinite function iteration and surreal numbers, \(\mathbb{N}\)-rationality of zeta functions, A ``Fourier transform for multiplicative functions on non-crossing partitions, A presentation of a finitely generated submonoid of invertible endomorphisms of the free monoid, On finite dimensional Nichols algebras of diagonal type, On the zero defect conjecture, Exchange of three intervals: substitutions and palindromicity, Testing for unboundedness of fifo channels, Equations over finite sets of words and equivalence problems in automata theory, On Simon's string searching algorithm, A square root map on Sturmian words, Partial orders on words, minimal elements of regular languages, and state complexity, Animaux et arbres guingois. (Animals and guingois trees), The Möbius function of factor order, Context-free grammars, differential operators and formal power series, Lyndon bases of free partially commutative Lie algebras, Properties of integers and finiteness conditions for semigroups, The decrease value theorem with an application to permutation statistics, On the minimal complexity of infinite words, Balancing and clustering of words in the Burrows-Wheeler transform, Linear-time computation of local periods, Hypernormal form theory: foundations and algorithms, Return time complexity of Sturmian sequences, Codes, orderings, and partial words, On the number of episturmian palindromes, On the complexity of decidable cases of the commutation problem of languages, A context-free and a 1-counter geodesic language for a Baumslag-Solitar group, Space efficient search for maximal repetitions, Generalised fine and Wilf's theorem for arbitrary number of periods, On a conjecture about finite fixed points of morphisms, Rational relations having a rational trace on each finite intersection of rational relations, A generalized palindromization map in free monoids, Problems in between words and abelian words: \(k\)-abelian avoidability, Characteristic Sturmian words are extremal for the critical factorization theorem, An extension of the Lyndon-Schützenberger result to pseudoperiodic words, On the number of frames in binary words, Regularity of sets of initial strings of periodic D0L-systems, La reconnaissance des facteurs d'un mot dans un texte, Optimal word chains for the Thue-Morse word, Sequences of words defined by two-way transducers, On fragments of words over a \(q\)-ary alphabet, The cycle lemma and some applications, Computation, on Macsyma, of the minimal differential representation of noncommutative polynomials, An algorithm for distinguishing efficiently bit-strings by their subsequences, A note on intersections of free submonoids of a free monoid, Occurrences of palindromes in characteristic Sturmian words, Structural properties of the string statistics problem, Rational languages and the Burnside problem, Systèmes codés. (Coded systems), Tight multiple twins in permutations, A property of three-element codes, On morphic generation of regular languages, On some equations in free partially commutative monoids, Notes on finitely generated semigroups and pumping conditions for regular languages, Parikh word representable graphs and morphisms, Systèmes entiers d'équations sur un alphabet fini et conjecture d'Ehrenfeucht, Minimal forbidden subwords, New permutation coding and equidistribution of set-valued statistics, A powerful abelian square-free substitution over 4 letters, On the defect theorem and simplifiability, From Nerode's congruence to suffix automata with mismatches, A formula for the determinant of a sum of matrices, Periodic D0L languages, Continuity of eigenfunctions of uniquely ergodic dynamical systems and intensity of Bragg peaks, Semi-commutations, Periodic and Sturmian languages, Weinbaum factorizations of primitive words, Circle formation of weak robots and Lyndon words, Identification of pattern languages from examples and queries, The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index, Farey codes and languages, Subword conditions and subword histories, Alternative proof of the Lyndon-Schützenberger theorem, A non-commutative formula for the colored Jones function, Nonrepetitive colorings of trees, Languages generated by iterated idempotency, Quasiperiodic Sturmian words and morphisms, The origins of combinatorics on words, On abelian 2-avoidable binary patterns, Pattern avoidance on graphs, On codes defined by bio-operations, Well quasi-orders generated by a word-shuffle rewriting, The formal Laplace--Borel transform of Fliess operators and the composition product, Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. II: Reconstruction with forbidden words, On prefixal factorizations of words, On periodic properties of circular words, Serial classification of fragments of words, Factorizations of free monoids and unavoidable regularities, Le support de l'algèbre de Lie libre. (Support of the free Lie algebra), A note on division orderings on strings, The Orlik-Solomon algebra on the partition lattice and the free Lie algebra, Palindrome positions in ternary square-free words, Discontinuities in pattern inference, Management and analysis of DNA microarray data by using weighted trees, Nonrepetitive colorings of graphs -- a survey, Thue type problems for graphs, points, and numbers, Fix-Mahonian calculus. I: Two transformations, Fix-Mahonian calculus. II: Further statistics, On the triplex substitution -- combinatorial properties, Marcus contextual languages consisting of primitive words, Kernel methods for learning languages, Combinatorics on words in symbolic dynamics: The antisymmetric cubic map, Combinatorics on words in symbolic dynamics: The quadratic map, Direct definition of a ternary infinite square-free sequence, Scattering matrices of regular coverings of graphs, Involutions of epicentral words, The entropy of square-free words, On bounded rational trace languages, A note on partially ordered tree automata, Optimality of some algorithms to detect quasiperiodicities, Growth rates of complexity of power-free languages, On maximal repetitions of arbitrary exponent, A cyclic binary morphism avoiding abelian fourth powers, On \(\theta\)-episturmian words, Palindromic richness, Overlap-freeness in infinite partial words, Computation of words satisfying the ``rhythmic oddity property (after Simha Arom's works), A class of relations among multiple zeta values, On smooth sets of integers, A classification of mahonian maj-inv statistics, Infinite periodic points of endomorphisms over special confluent rewriting systems, Twin-roots of words and their properties, Morphically primitive words, Asymptotic behavior of beta-integers, On primary and secondary repetitions in words, Cyclically repetition-free words on small alphabets, On the Shyr-Yu theorem, A characterization of regular circular languages generated by marked splicing systems, Gröbner-Shirshov bases for associative algebras with multiple operators and free Rota-Baxter algebras., Balanced words and dynamical systems, Mould calculus: from primary to secondary mould symmetries, Signed words and permutations. V: A sextuple distribution, Chen-Fox-Lyndon factorization for words over partially ordered sets, On graphs of central episturmian words, The maximal-inversion statistic and pattern-avoiding permutations, The structure of connected (graded) Hopf algebras, Witt vectors and the algebra of necklaces, On the Burnside problem for semigroups, The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids, The shuffle algebra on the factors of a word is free, On the product of square-free words, On three-element codes, Macsyma computation of local minimal realization of dynamical systems of which generating power series are finite, Optimal superprimitivity testing for strings, On finitely recognizable semigroups, Exponents of Diophantine approximation in dimension 2 for a general class of numbers, Indeterminate string factorizations and degenerate text transformations, Word-representability of split graphs generated by morphisms, Factorizing strings into repetitions, Dynamical directions in numeration, On systems of word equations with simple loop sets, A note on the number of squares in a word, Transposition invariant words, Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words, Infinite unfair shuffles and associativity, Words that almost commute, A characterization of binary morphisms generating Lyndon infinite words, Equations over the \(k\)-binomial monoids, Algorithms for subsequence combinatorics, Long binary patterns are abelian 2-avoidable, Quasiperiodic and Lyndon episturmian words, Existence of finite test-sets for \(k\)-power-freeness of uniform morphisms, On a factorization of graded Hopf algebras using Lyndon words., PBW bases for a class of braided Hopf algebras., Constructions of free dibands and tribands, New algebraic and geometric constructs arising from Fibonacci numbers., On the topological convergence of multi-rule sequences of sets and fractal patterns, Description of normal bases of boundary algebras and factor languages of slow growth, Subshifts with leading sequences, uniformity of cocycles and spectra of Schreier graphs, Two strings at Hamming distance 1 cannot be both quasiperiodic, Equations over free inverse monoids with idempotent variables, Can we recover the cover?, A characterization of free pairs of upper triangular free monoid morphisms, A new weighted Ihara zeta function for a graph, Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness, Exact and asymptotic enumeration of cyclic permutations according to descent set, Euler-Mahonian triple set-valued statistics on permutations, Weighted Bartholdi zeta functions of graph coverings, Ruelle zeta functions for finite digraphs, The identity problem of finitely generated bi-ideals, On new chaotic mappings in symbol space, Uniform convergence of Schrödinger cocycles over simple Toeplitz subshift, Generalization of convolution and incidence algebras, Iterated periodicity over finite aperiodic semigroups, Towards optimal packed string matching, Some weighted Bartholdi zeta function of a digraph, A \(q\)-multinomial expansion of LLT coefficients and plethysm multiplicities, On generalized highly potential words, Characterization of the lengths of binary circular words containing no squares other than 00, 11, and 0101, Closest periodic vectors in \(L_p\) spaces, Conserved energies for the one dimensional Gross-Pitaevskii equation, Permuting operations on strings and the distribution of their prime numbers, An efficient Gray code algorithm for generating all permutations with a given major index, Avoiding abelian powers cyclically, 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, Abelian closures of infinite binary words, On complexity of grammars related to the safety problem, Mirror substitutions and palindromic sequences, Relational codes of words, Freeness of partial words, Quasi-periodic continued fractions, Prefix-primitivity-preserving homomorphisms, Hybrid and generalized marked systems, On an involution of Christoffel words and Sturmian morphisms, Shuffle operations on discrete paths, Completing circular codes in regular submonoids, Breaking the rhythm on graphs, Reconstructing compositions, Monomial algebras defined by Lyndon words., A basis for the right quantum algebra and the ``\(1= q\) principle, Smooth words on 2-letter alphabets having same parity, Unbordered factors and Lyndon words, Connections between subwords and certain matrix mappings, Counting bordered and primitive words with a fixed weight, Commutation with codes, Primitive partial words, Weighted Bartholdi zeta functions of graphs, Recognizable subsets of some partially Abelian monoids, On the number of \(\alpha \)-power-free binary words for \(2<\alpha \leq 7/3\), Characteristic morphisms of generalized episturmian words, On systems of word equations over three unknowns with at most six occurrences of one of the unknowns, Simple equations on binary factorial languages, Burrows-Wheeler transform and palindromic richness, Hairpin structures defined by DNA trajectories, Optimal bounds for computing \({\alpha}\)-gapped repeats, Implicit operations on finite \({\mathcal J}\)-trivial semigroups and a conjecture of I. Simon, Cartesian and Lyndon trees, Embedding a \(\theta \)-invariant code into a complete one, Finitely distinguishable erasing pattern languages, Extremal square-free words, Queens in exile: non-attacking queens on infinite chess boards, Free monoids and generalized metric spaces, On the size of the smallest alphabet for Lyndon trees, Approximate cover of strings, Some further results on squarefree arithmetic progressions in infinite words, How to play Thue games, Approximate periodicity, Perspectives: Journal of Discrete Algorithms Special StringMasters Issue (2015), Classification of sub-Cuntz states, Characterization of repetitions in Sturmian words: a new proof, Privileged factors in the Thue-Morse word -- a comparison of privileged words and palindromes, Rich square-free words, On uniformly repetitive semigroups, Infinite words and biprefix codes, Average cost of Duval's algorithm for generating Lyndon words, Well quasi-orders and regular languages, Automata calculating the complexity of automatic sequences, Weights for total division orderings on strings, Some combinatorial properties of Sturmian words, Viennot factorization of infinite words, On the size of independent systems of equations in semigroups, On the language of primitive words, Infinite self-similar words, Automata accepting primitive words, Some stochastic processes in a random permutation, Theory of traces, On the length of word chains, Notes on congruence relations and factor pumping conditions for rational languages, Saving comparisons in the Crochemore-Perrin string-matching algorithm, On recognizable subsets of free partially commutative monoids, Partially ordered finite monoids and a theorem of I. Simon, Fibonacci numbers and words, The zooming method: A recursive approach to time-space efficient string-matching, Shuffle of parenthesis systems and Baxter permutations, Permutation properties and the Fibonacci semigroup, La reconnaissance des facteurs d'un langage fini dans un texte en temps linéaire. (Recognition of the factors of a finite language in a text in linear time), Solvability of the asynchronous ranking problem, A note on word chains and regular languages, Caractérisation des ensembles normaux substitutifs. (Characterization of normal substitutional sets), The algebra of implicit operations, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Factorial languages whose growth function is quadratically upper bounded, \(\alpha\)-words and factors of characteristic sequences, A necessary condition for the rationality of the zeta function of a regular language, Algebraic and multiple integral identities, Cycle type and descent set in wreath products, On the descriptive power of special Thue systems, The set of minimal words of a context-free language is context-free, Shuffle on trajectories: Syntactic constraints, Inventories of unavoidable languages and the word-extension conjecture, On sequences resulting from iteration of modified quadratic and palindromic mappings, Sturmian words: structure, combinatorics, and their arithmetics, Sturmian words, Lyndon words and trees, Standard Sturmian morphisms, On the factors of automatic words, A representation theorem of the suffixes of characteristic sequences, Conjugacy and episturmian morphisms., Finding approximate repetitions under Hamming distance., Hierarchical structures in Sturmian dynamical systems, Some properties of the factors of Sturmian sequences., Cumulants, lattice paths, and orthogonal polynomials, On the independence of equations in three variables., Lyndon words, permutations and trees., Topologies for the free monoid, Automatic average-case analysis of algorithms, Anti-exceedances in permutation groups, Finiteness and iteration conditions for semigroups, Fibonacci morphisms and Sturmian words, Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Permutation statistics and linear extensions of posets, Efficient parallel algorithms to test square-freeness and factorize strings, On generalized zeta functions of formal languages and series, Trace monoids with some invertible generators: Two decision problems, Strongly compatible total orders on free monoids, A hyperoctahedral analogue of the free Lie algebra, Polynomial operations and hierarchies of concatenation, Applications of a noncommutative Jacobian matrix, Languages whose \(n\)-element subsets are codes, Every binary pattern of length six is avoidable on the two-letter alphabet, Outfix and infix codes and related classes of languages, Mahonian statistics on labeled forests, On noncounting regular classes, Power of words and recognizability of fixpoints of a substitution, Rational series with coefficients in a commutative ring, The free partially commutative Lie algebra: Bases and ranks, Birthday paradox, coupon collectors, caching algorithms and self- organizing search, Homomorphisms between Solomon's descent algebras, On the regularity of languages on a binary alphabet generated by copying systems, Efficient CRCW-PRAM algorithms for universal substring searching, An on-line string superprimitivity test, The shuffle algebra and its derivations, A note on \(\omega\)-permutable semigroups, How many squares can a string contain?, Periodicities on trees, Unbordered factors of the characteristic sequences of irrational numbers, A conjecture on continued fractions, On well quasi orders of free monoids, On quasi orders of words and the confluence property, Intertwinings of periodic sequences, On the combinatorics of finite words, Lyndon words and singular factors of sturmian words, Fine and Wilf's theorem for three periods and a generalization of Sturmian words, Generalized factorizations of words and their algorithmic properties, Quasiperiodicity and string covering, Gröbner-Shirshov bases for Lie superalgebras and their universal enveloping algebras, A characterization of overlap-free morphisms, On a combinatorial property of Fibonacci semigroup, Counting permutations with given cycle structure and descent set, On bispecial factors of the Thue-Morse word, Testing string superprimitivity in parallel, Sturmian morphisms and Rauzy's rules, \(p\)-adic topology on words, RATIONAL APPROXIMATIONS OF POLYNOMIAL FACTORIAL LANGUAGES, Equations in the Partial Semigroup of Words with Overlapping Products, A proof of Dejean’s conjecture, Transfinite Lyndon Words, The number of cycles with a given descent set, Avoiding letter patterns in ternary square-free words, ON THE EXISTENCE OF MINIMAL β-POWERS, Overlaps in free partially commutative monoids, Efficient solution of some problems in free partially commutative monoids, Plain and Twisted Adjoints of Well-Formed Words, Squarefree words with interior disposable factors, Dense property of initial literal shuffles, A combinatorial theorem on $p$-power-free words and an application to semigroups, Gamma positivity of the excedance-based Eulerian polynomial in positive elements of classical Weyl groups, Primitive sets of words, A generalized variety problem, Elementariness of a finite set of words is co-NP-complete, On the Step-Patterns of Generated Scales that are Not Well-Formed, Linear construction of a left Lyndon tree, The structure of connected (graded) Hopf algebras revisited, Complementary symmetric Rote sequences: the critical exponent and the recurrence function, On the Suffix Automaton with Mismatches, Locally countable pseudovarieties, Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis, Uniformly bounded duplication codes, An algorithm for periodicity and almost periodicity of uniform substitution sequences and its implications on aperiodic spin models, On patterns occurring in binary algebraic numbers, Some Algebraic Properties of Machine Poset of Infinite Words, From Bi-ideals to Periodicity, ON INEQUALITIES BETWEEN SUBWORD HISTORIES, PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS, Computable symbolic dynamics, On the Continued Fraction Expansion of a Class of Numbers, The Average State Complexity of the Star of a Finite Set of Words Is Linear, On a Generalization of Standard Episturmian Morphisms, Large Simple Binary Equality Words, Duplication in DNA Sequences, An Analysis and a Reproof of Hmelevskii’s Theorem, PBW-bases of coideal subalgebras and a freeness theorem, A hierarchy for circular codes, Look and Say Fibonacci, Periodicity Problem of Substitutions over Ternary Alphabets, Fliess series, a generalization of the Ree's theorem, and an algebraic approach to a homogeneous approximation problem, On a paper by Castelli, Mignosi, Restivo, The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings, Injective envelopes of transition systems and Ferrers languages, Equations on partial words, Periodic codings of Bratteli-Vershik systems, On the Maximal Sum of Exponents of Runsin a String, Two-variable word equations, Local Squares, Periodicity and Finite Automata, What Is Essential Unification?, Compressed Membership in Automata with Compressed Labels, String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time, Simple Real-Time Constant-Space String Matching, ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS, MINIMAL DUVAL EXTENSIONS, Codes et motifs, Quasi-Monotonic Sequences: Theory, Algorithms and Applications, Some characterizations of finite Sturmian words., On unique factorizations of primitive words., Non-uniform random generation of generalized Motzkin paths, Two-parameter Quantum Groups of Exceptional Type E-Series and Convex PBW-type Basis, On a Special Class of Primitive Words, Independence of certain quantities indicating subword occurrences, Pseudopalindrome closure operators in free monoids, The power conjugacy problem in Higman–Thompson groups, Rational Selecting Relations and Selectors, On the index of Simon's congruence for piecewise testability, A NEW PROOF OF THE THREE-SQUARES LEMMA FOR PARTIAL WORDS WITH ONE HOLE, On a Family of Morphic Images of Arnoux-Rauzy Words, Theories of orders on the set of words, Splitting necklaces and measurable colorings of the real line, Directive words of episturmian words: equivalences and normalization, ALGEBRAIC LINEAR ORDERINGS, Rich and Periodic-Like Words, An Extension of the Lyndon Schützenberger Result to Pseudoperiodic Words, On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations, Two-Sided Bounds for the Growth Rates of Power-Free Languages, COMPUTING MORPHISMS BY SPIKING NEURAL P SYSTEMS, ON PARTITIONS SEPARATING WORDS, SOME EXTREMAL PROPERTIES OF THE FIBONACCI WORD, A NEW COMPLEXITY FUNCTION FOR WORDS BASED ON PERIODICITY, On the power of circular splicing, Inequalities characterizing standard Sturmian and episturmian words, Signed words and permutations, I: A fundamental transformation, A simple proof that a word of length \(n\) has at most \(2n\) distinct squares, Transition matrices and kronecker product expansions of symmetric functions, The existential theory of equations with rational constraints in free groups is PSPACE-complete, Compound Poisson approximation of word counts in DNA sequences, The non-parametrizability of the word equation \(xyz=zvx\): a short proof, 𝑞-Eulerian polynomials: Excedance number and major index, A multidimensional critical factorization theorem, Three dimensional Narayana and Schröder numbers, Braided version of Shirshov-Witt theorem, Automorphisms of subword-posets, On the Lifting of Nichols Algebras, On Conjugacy of Languages, A test-set fork-power-free binary morphisms, Linear size test sets for certain commutative languages, The geometric properties of an infinitary line and plane languages, Single-tape reset machines, Unnamed Item, Unnamed Item, Density of Critical Factorizations, ON SEPARABILITY FINITENESS CONDITIONS IN SEMIGROUPS, Zeta Functions of Formal Languages, Reducibility vs. definability for pseudovarieties of semigroups, Sul problema di Burnside per i semigruppi e i linguaggi, Context-free languages consisting of non-primitive words, Critical factorisation in square-free words, On primitive words with non-primitive product, Estimates in Shirshov height theorem, Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif, A note on thue systems with a single defining relation, Asymptotic behaviour of bi-infinite words, Circular splicing and regularity, Repetitions in the Fibonacci infinite word, Numeration systems, linear recurrences, and regular sets, Enumeration of bordered words, le langage de la vache-qui-rit, Une extension d'un théorème de P. Jullien sur les âges de mots, Lie algebraic representation results for nonstationary evolution operators, On the character of words of sublinear complexity, Nil properties for rings which are sums of their additive subgroups, New results on the generalized star-height problem, Compression and entropy, One-rule trace-rewriting systems and confluence, Efficient solving of the word equations in one variable, Some trace monoids where both the Star problem and the Finite Power Property Problem are decidable, Random graph languages, Parties reconnaissables de monoïdes définis par générateurs et relations, Chomsky-Schützenberger Type Characterizations of Poly-Slender and Parikh Slender Context-Free Languages1 1Work supported by the Grants-in Aid for Scientific Research No. 1 0440034, Japan Society for the Promotion of Sciences and the Dirección General de Enseñanza Superior e Investigación Cientifica, SB 97-00110508, Derived sequences of complementary symmetric Rote sequences, Unavoidable languages, cuts and innocent sets of words, The “Runs” Theorem, The local Hölder exponent for the dimension of invariant subsets of the circle, Towards parametrizing word equations, Calcul de la distance par les sous-mots, Codes limites et factorisations finies du monoïde libre, Restricted Burnside problem for semigroups and its application to language theory, A linear-time algorithm to decide whether a binary word contains an overlap, General Framework, Coloring Problems for Infinite Words, $k$-Arrangements, Statistics, and Patterns, Detecting the morphic images of a word : improving the general algorithm, Characterization of Infinite LSP Words and Endomorphisms Preserving the LSP Property, A characterization of words of linear complexity, Bisections reconnaissables, The product of rational languages, Monoïde libre et musique : deuxième partie, Decimations and sturmian words, Polynomial size test sets for commutative languages, A uniform cube-free morphism isk-power-free for all integersk≥ 4, Generalized cancellation-and-permutation properties, regular languages and supports of rational series, Greedy Palindromic Lengths, Approximation of Multiple Stochastic Integrals and Its Application to Stochastic Differential Equations, The Karoubi envelope of the mirage of a subshift, Disjunctive languages and compatible orders, Generic Algorithms for Factoring Strings, Unnamed Item, Languages obtained from infinite words, Multibasic Eulerian Polynomials, Factorisation des ensembles préfixiels, Unnamed Item, Standard Lyndon Bases of Lie Algebras and Enveloping Algebras, CHANNEL SYNTHESIS FOR FINITE TRANSDUCERS, LARGE SIMPLE BINARY EQUALITY WORDS, On Shuffle Ideals, Unnamed Item, On the number of squares in partial words, On the growth rates of complexity of threshold languages, Unnamed Item, Unnamed Item, Unnamed Item, Abelian squares are avoidable on 4 letters, Music and combinatorics on words: a historical survey, Functions for parametrization of solutions of an equation in a free monoid, Unnamed Item, Parikh q-Matrices and q-Ambiguous Words, Unnamed Item, On winning shifts of marked uniform substitutions, INFINITE WORDS AND CONFLUENT REWRITING SYSTEMS: ENDOMORPHISM EXTENSIONS, The Quantifier Alternation Hierarchy of Synchronous Relations, Square-free extensions of words, On the size of independent systems of equations in semigroups, Half-line eigenfunction estimates and purely singular continuous spectrum of zero Lebesgue measure, Outils et résultats pour les transducteurs boustrophédons, An efficient algorithm for computing the Baker–Campbell–Hausdorff series and some of its applications, Unnamed Item, n-Prefix–suffix languages∗, Dejean's conjecture holds for N ≥ 27, Unnamed Item, A combinatorial property and growth for semigroups of matrices, A characterization of poly-slender context-free languages, A correspondence between a class of monoids and self-similar group actions II, Unnamed Item, Almost linear time computation of maximal repetitions in run length encoded strings, A Combinatorial Proof of Bass’s Evaluations of the Ihara-Selberg Zeta Function for Graphs, Longest Lyndon Substring After Edit, Quasi-Periodicity Under Mismatch Errors, Long twins in random words, Singleton mesh patterns in multidimensional permutations, The second step in characterizing a three-word code, Enumeration of partial Łukasiewicz paths, On endomorphisms of the direct product of two free groups, String rearrangement inequalities and a total order between primitive words, Confluence of one-rule Thue systems, Systems of equations over a finite set of words and automata theory, On the Solution Sets of Entire Systems of Word Equations, A rewriting of Fife's theorem about overlap-free words, A Note on Squares in Binary Words, Regularity of k-Abelian Equivalence Classes of Fixed Cardinality, Makanin's algorithm for word equations-two improvements and a generalization, Extensions and reductions of squarefree words, Unnamed Item, WORD COMPLEXITY AND REPETITIONS IN WORDS, Languages and P0L schemes, On the number of partially abelian square-free words on a three-letter alphabet, Consistency rates and asymptotic normality of the high risk conditional for functional data, Toeplitz words, generalized periodicity and periodically iterated morphisms, A characterization of Sturmian words by return words, Semigroups of zero entropy, Consistency rates and asymptotic normality of the high risk conditional for functional data, Skew primitive elements in Hopf algebras and related identities, On codes with a finite deciphering delay: Constructing uncompletable words, Codes and equations on trees, The growth function of context-free languages, Words and special factors, Solving word equations, Partially abelian squarefree words, Upper bounds for the complexity of sequences generated by symmetric Boolean functions, Zeta functions of digraphs, The algebra of quasi-symmetric functions is free over the integers, Local and global cyclicity in free semigroups, Partial words and a theorem of Fine and Wilf revisited, Direct and dual laws for automata with multiplicities, Confluent Parry numbers, their spectra, and integers in positive- and negative-base number systems, Unavoidable sets, COMBINATORIAL PROPERTIES OF STURMIAN PALINDROMES, UNAMBIGUOUS MORPHIC IMAGES OF STRINGS, SUBWORD COMPLEXITY OF PROFINITE WORDS AND SUBGROUPS OF FREE PROFINITE SEMIGROUPS, Nonrepetitive colorings of graphs, WHEN THUE-MORSE MEETS KOCH, On the number of word occurrences in a semi-Markov sequence of letters, The Foata correspondence, cycle lengths and anomalies, Complete dynamical evaluation of the characteristic polynomial of binary quantum graphs
