scientific article; zbMATH DE number 1024080

zbMath0874.20040MaRDI QIDQ4341774

Publication date: 18 June 1997

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

automata free semigroups nilpotent groups Lie algebras algebras with polynomial identities free algebras formal languages free monoids combinatorics on words asymptotic properties of words

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Combinatorics on words (68R15) Formal languages and automata (68Q45) 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

New results on Nyldon words and Nyldon-like sets, Sufficient conditions for the marked graph realisability of labelled transition systems, Clusters of repetition roots: single chains, Morphic sequences versus automatic sequences, Lyndon words formalized in Isabelle/HOL, A ternary square-free sequence avoiding factors equivalent to $abcacba$, Finding the leftmost critical factorization on unordered alphabet, Lyndon + Christoffel = digitally convex, Classification of eventually periodic subshifts, Generalized Pascal triangle for binomial coefficients of words, Perfect necklaces, Leaf realization problem, caterpillar graphs and prefix normal words, Avoidance bases for formulas with reversal, The quaternionic weighted zeta function of a graph, Several extensions of the Parikh matrix $L$-morphism, Longest common subsequence problem for unoriented and cyclic strings, The origins of combinatorics on words, Zero-measure Cantor spectrum for Schrödinger operators with low-complexity potentials, Definability in the structure of words with the inclusion relation, Equivalence of simple functions, On a generalization of abelian equivalence and complexity of infinite words, Abelian-primitive partial words, Tree shuffle, A linear partitioning algorithm for hybrid Lyndons using $V$-order, The total run length of a word, Combinatorial properties of double square tiles, Regular languages and partial commutations, Lyndon words and Fibonacci numbers, Linear computation of unbordered conjugate on unordered alphabet, Infinite words containing the minimal number of repetitions, Computing the partial word avoidability indices of binary patterns, Computing the partial word avoidability indices of ternary patterns, A generalization of de Bruijn graphs and classification of endomorphisms of Cuntz algebras by graph invariants, On the maximality of languages with combined types of code properties, A presentation by generators and relations of Nichols algebras of diagonal type and convex orders on root systems., Biinfinite words with maximal recurrent unbordered factors., The three squares lemma revisited, The $(1-\mathbb{E})$-transform in combinatorial Hopf algebras, A parallelogram tile fills the plane by translation in at most two distinct ways, Two infinite families of polyominoes that tile the plane by translation in two distinct ways, Periodicity algorithms and a conjecture on overlaps in partial words, Recent results on syntactic groups of prefix codes., Avoiding Abelian squares in partial words, Algorithmic complexity of protein identification: Combinatorics of weighted strings, Fewest repetitions versus maximal-exponent powers in infinite binary words, Graph connectivity, partial words, and a theorem of Fine and Wilf, Composition-diamond lemma for associative conformal algebras., Some kinds of primitive and non-primitive words, On generating binary words palindromically, Reconstruction of a word from a multiset of its factors, The pseudopalindromic completion of regular languages, Finite automata for testing composition-based reconstructibility of sequences, An algorithmic toolbox for periodic partial words, Substitutions on two letters, cutting segments and their projections, An algorithm for enumerating all infinite repetitions in a D0L-system, Square-free shuffles of words, Another generalization of abelian equivalence: binomial complexity of infinite words, Palindromic sequences generated from marked morphisms, The quaternionic second weighted zeta function of a graph and the Study determinant, New identities in dendriform algebras, Relations on words, Binary block order Rouen transform, Two fast constructions of compact representations of binary words with given set of periods, On the density of Lyndon roots in factors, Multiplicity of positive periodic solutions in the superlinear indefinite case via coincidence degree, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Deciding game invariance, Solutions to the multi-dimensional Prouhet-Tarry-Escott problem resulting from composition of balanced morphisms, Behavior of digital sequences through exotic numeration systems, Languages with membership determined by single letter factors, Disjunctivity and other properties of sets of pseudo-bordered words, Dependence with complete connections and the Gauss-Kuzmin theorem for $N$-continued fractions, Representations of Khovanov-Lauda-Rouquier algebras and combinatorics of Lyndon words., Higher-order matching polynomials and $d$-orthogonality, Extensions and restrictions of Wythoff's game preserving its $\mathcal P$ positions, Quantum quasi-shuffle algebras., Equations on palindromes and circular words, Spiraling and folding: the word view, Avoiding large squares in partial words, The formal series Witt transform, Border correlations of partial words, On Christoffel and standard words and their derivatives, On uniformly continuous functions for some profinite topologies, The extended equation of Lyndon and Schützenberger, On the tiling by translation problem, A generalization of Thue freeness for partial words, On structural properties of eta-expansions of identity, On finitely generated idempotent semigroups., Intersecting periodic words, On highly palindromic words, Two linear-time algorithms for computing the minimum length polygon of a digital contour, Avoidable binary patterns in partial words, A characterization of rational D0L power series, Long cycles in $abc$-permutations, Primitive partial permutation representations of the polycyclic monoids and branching function systems., Gauss sums, Jacobi sums, and $p$-ranks of cyclic difference sets, Some results on $k$-power-free morphisms, Quantum evolution of words, Avoidability index for binary patterns with reversal, Transitive sofic spacing shifts, On Boolean combinations forming piecewise testable languages, Scattered Factor-Universality of Words, Reconstructing Words from Right-Bounded-Block Words, Hidden automatic sequences, On the complexity of infinite words generated by countable $q$-automata, Substitutions with cofinal fixed points, Prefix-Suffix Square Completion, On the distribution of characteristic parameters of words, On the distribution of characteristic parameters of words II, Palindromic Complexity of Trees, Unary Patterns with Permutations, On the Complexity of k-Piecewise Testability and the Depth of Automata, On the decidability of semigroup freeness, Computing equality-free and repetitive string factorisations, Fewest repetitions in infinite binary words, An aperiodicity problem for multiwords, Unnamed Item, Newton series, coinductively: a comparative study of composition, Newton’s Forward Difference Equation for Functions from Words to Words, The geometry of the consequences of a single Engel relator., Counting Lyndon factors, The algebraic entropy of classical mechanics, Identities and derivative formulas for the combinatorial and Apostol-Euler type numbers by their generating functions, String Powers in Trees, Greek Ethnic Modal Names vs. Alia Musica’s Nomenclature, Algebras defined by Lyndon words and Artin-Schelter regularity, On the automorphism group of minimal -adic subshifts of finite alphabet rank, Computing Primitively-Rooted Squares and Runs in Partial Words, Counting (Watson-Crick) palindromes in Watson-Crick conjugates, Avoiding square-free words on free groups, Enumeration of two dimensional palindromes, Avoiding squares over words with lists of size three amongst four symbols, Random graph languages, On Prefix/Suffix-Square Free Words, Constructing Words with High Distinct Square Densities, Computing Depths of Patterns, On generalized Lyndon words, Analysis of generating functions for special words and numbers and algorithms for computation, Positive solutions for super-sublinear indefinite problems: High multiplicity results via coincidence degree, Coverability and multi-scale coverability on infinite pictures, An analog of the prime number theorem for finite fields via truncated polylogarithm expansions, Strong representations of the polycyclic inverse monoids: cycles and atoms., Defect theorem in the plane, Arithmetical complexity of the language of generic limit sets of cellular automata, A morphic approach to combinatorial games: the Tribonacci case, Most pseudo-copy languages are not context-free, Absent subsequences in words, Substitutions, symbolic codings, and discrepancy, Squares in partial words, A noncommutative extension of Mahler's theorem on interpolation series, A bijective variant of the Burrows-Wheeler transform using $V$-order, Unnamed Item, On the atoms of algebraic lattices arising in 𝔮-theory, Subsequence Counting, Matrix Representations and a Theorem of Eilenberg, How Many Figure Sets Are Codes?, A coloring problem for infinite words, Hopf algebras and Markov chains: two examples and a theory, From Combinatorial Games to Shape-Symmetric Morphisms, Decoding Genomic Information, Least Periods of Factors of Infinite Words, Continued fractions with $SL(2, Z)$-branches: combinatorics and entropy, Non-primitive words of the formpq^m, Properties of Parikh Matrices of Binary Words Obtained by an Extension of a Restricted Shuffle Operator, On a class of infinite words with affine factor complexity, Generalizations of Parikh mappings, Reconstruction of hv-convex Binary Matrices from Their Absorbed Projections, Codes of central Sturmian words, Substitution dynamical systems: characterization of linear repetitivity and applications, A condition of Boshernitzan and uniform convergence in the multiplicative ergodic theorem, Unnamed Item, 3-Way Composition of Weighted Finite-State Transducers, Avoiding Two Consecutive Blocks of Same Size and Same Sum over $\mathbb{Z}^2$, Classifications of dense languages, Coverability in Two Dimensions, A Multiset Version of Even-Odd Permutations Identity, Creating improvisations on chord progressions using suffix trees, An Answer to a Conjecture on Overlaps in Partial Words Using Periodicity Algorithms, Unnamed Item, Graph Logics with Rational Relations, k-Abelian Equivalence and Rationality, Wiener-type indices of Parikh word representable graphs, Definability in the Infix Order on Words, A Mahler's Theorem for Word Functions, Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence, ABOUT THE MULTIFRACTAL NATURE OF CANTOR’S BIJECTION: BOUNDS FOR THE HÖLDER EXPONENT AT ALMOST EVERY IRRATIONAL POINT, Unnamed Item, Purely singular continuous spectrum for Sturmian CMV matrices via strengthened Gordon Lemmas, Christoffel and Fibonacci Tiles, Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour, Unnamed Item, Roots and Powers in Regular Languages: Recognizing Nonregular Properties by Finite Automata, On some root multiplicities for Nichols algebras of diagonal type over arbitrary fields, Unnamed Item, A sufficient condition for non-uniqueness in binary tomography with absorption, Algebras of Finite Global Dimension, Sturmian words and the Stern sequence, Cubic patterns with permutations, Studies on finite Sturmian words, Identities for Dirichlet and Lambert-type series arising from the numbers of a certain special word, Computation of k-ary Lyndon words using generating functions and their differential equations, Powers in Sturmian sequences, The eigenvalues of hyperoctahedral descent operators and applications to card-shuffling, Uniform words, A pair of dual Hopf algebras on permutations, A bijection for triangulations of a polygon with interior points and multiple edges, Rauzy induction of polygon partitions and toral $\mathbb{Z}^2$-rotations, A decomposition of ballot permutations, pattern avoidance and Gessel walks, Document spanners: from expressive power to decision problems, On the word fragment length for unambiguous reconstruction of a periodic word from a complete multiset of fragments of fixed length, Gray codes for Fibonacci $q$-decreasing words, Fixed points of Sturmian morphisms and their derivated words, Unary patterns under permutations, Can formal languages help pangenomics to represent and analyze multiple genomes?, Binomial complexities and Parikh-collinear morphisms, Asymptotic analysis of $q$-recursive sequences, The number of configurations in the full shift with a given least period, String cadences, On the group of a rational maximal bifix code, Positive subharmonic solutions to superlinear ODEs with indefinite weight, Computing primitively-rooted squares and runs in partial words, String powers in trees, Finiteness properties of direct products of algebraic structures, Bijections between Łukasiewicz walks and generalized tandem walks, Reprint of: ``Generalized Lyndon factorizations of infinite words, $k$-ary Lyndon words and necklaces arising as rational arguments of Hurwitz-Lerch zeta function and Apostol-Bernoulli polynomials, Algebraic properties of Parikh matrices of binary picture arrays, Morphisms generating antipalindromic words, Circular words and three applications: factors of the Fibonacci word, $\mathcal F$-adic numbers, and the sequence $1, 5, 16, 45, 121, 320,\dots$, Bifix codes and Sturmian words, Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile, A noncommutative cycle index and new bases of quasi-symmetric functions and noncommutative symmetric functions, Hide and seek with repetitions, Cycle Lemma, parking functions and related multigraphs, Numerical evaluation of special power series including the numbers of Lyndon words: an approach to interpolation functions for Apostol-type numbers and polynomials, On sets of indefinitely desubstitutable words, On the minimal alphabet size in multidimensional unrepetitive configurations, Some algorithmic problems for Poisson algebras, Cadences in grammar-compressed strings, Trimming the permutahedron to extend the parking space, On interpolation functions for the number of $k$-ary Lyndon words associated with the Apostol-Euler numbers and their applications, Palindromic trees for a sliding window and its applications, The connective eccentricity index and modified second Zagreb index of Parikh word representable graphs, Patterns in the generalized Fibonacci word, applied to games, Square network on a word, Block reversal on finite words, Anti-powers in infinite words, An equivalence of multistatistics on permutations, Some variations on a theme of Irina Mel'nichuk concerning the avoidability of patterns in strings of symbols, Convergence of Pascal-like triangles in Parry-Bertrand numeration systems, Conserved energies for the cubic nonlinear Schrödinger equation in one dimension, On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties, Disposability in square-free words, Computing regularities in strings: a survey, Avoiding 2-binomial squares and cubes, Lyndon factorization algorithms for small alphabets and run-length encoded strings, Some results on extensionality in lambda calculus, Equivalence classes of matchings and lattice-square designs, Dynamical upper bounds for one-dimensional quasicrystals, Compatibility and conjugacy on partial arrays, Semigroups arising from asynchronous automata., Some operations preserving primitivity of words, Towards the n-point one-loop superstring amplitude. I: Pure spinors and superfield kinematics, Towards the $n$-point one-loop superstring amplitude. II: Worldsheet functions and their duality to kinematics, Counting and ordering periodic stationary solutions of lattice Nagumo equations, Classes of languages generated by the Kleene star of a word, Homotopy groups of highly connected manifolds, (Pure) transcendence bases in $\varphi$-deformed shuffle bialgebras, Hopf algebra structure of generalized quasi-symmetric functions in partially commutative variables, A Rauzy fractal unbounded in all directions of the plane, On the least number of palindromes in two-dimensional words, Inverse Lyndon words and inverse Lyndon factorizations of words, Certain distance-based topological indices of Parikh word representable graphs, Minimal automaton for multiplying and translating the Thue-Morse set, On conflict free DNA codes, Statistics on multipermutations and partial $\gamma$-positivity, Quasiperiods of biinfinite words, Operations on Christoffel words, On equations and first-order theory of one-relator monoids, Pseudo-solutions of word equations, Greedy approximations by signed harmonic sums and the Thue-Morse sequence, Substitutive systems and a finitary version of Cobham's theorem, Nyldon words, Reconstruction of $hv$-convex binary matrices from their absorbed projections, On PSPACE generation of a solution set of a word equation and its applications, A multiset version of determinants and the coin arrangements lemma, Applications of Apostol-type numbers and polynomials: approach to techniques of computation algorithms in approximation and interpolation functions, Growth of structure constants of free Lie algebras relative to Hall bases, Further steps on the reconstruction of convex polyominoes from orthogonal projections, Lumpings of algebraic Markov chains arise from subquotients, Languages and formations generated by $D_4$ and $Q_8$, Obituary: Aldo de Luca 1941--2018, KK-like relations of $\alpha^\prime$ corrections to disk amplitudes, Entropy of generating series for nonlinear input-output systems and their interconnections, Conjugacy on partial words., Squares and primitivity in partial words, Algebraic properties of word equations, A noncommutative extension of Mahler's interpolation theorem, Clusters of repetition roots forming prefix chains, Nearly $k$-universal words -- investigating a part of Simon's congruence, A periodicity lemma for partial words, Automatic sequences: from rational bases to trees, Down-step statistics in generalized Dyck paths, Asymptotic behavior of some factorizations of random words, Lattice Paths and Branched Continued Fractions: An Infinite Sequence of Generalizations of the Stieltjes–Rogers and Thron–Rogers Polynomials, with Coefficientwise Hankel-Total Positivity, A simple homological characterization of string algebras of finite representation type, Absent Subsequences in Words, Languages generated by conjunctive query fragments of FC[REG], Rooted quasi-Stirling permutations of general multisets, Abelian combinatorics on words: a survey, Two-dimensional Fibonacci words: tandem repeats and factor complexity, Watson-Crick powers of a word, Lyndon partial words and arrays with applications, Matching patterns with variables under edit distance, On the number of distinct $k$-decks: enumeration and bounds, HV-Palindromes in Two-Dimensional Words, A Lie bracket for the momentum kernel, Lie structure of the Heisenberg-Weyl algebra, Decidable problems in substitution shifts, Minimal Complexities for Infinite Words Written with d Letters, Ranking and Unranking k-Subsequence Universal Words, String Attractors of Fixed Points of k-Bonacci-Like Morphisms, An investigation to test spectral segments as bacterial biomarkers, Tree-level amplitudes from the pure spinor superstring, Rich words in the block reversal of a word, On the decomposability of homogeneous binary planar configurations with respect to a given exact polyomino, Unnamed Item, The k-centre problem for classes of cyclic words, A unified framework for double sweep methods for the Helmholtz equation, On forced periodicity of perfect colorings, A tight upper bound on the length of maximal bordered box repetition-free words, Combinatorial approach of unified Apostol-type polynomials using $\alpha $-distanced words, Characterizations of families of morphisms and words via binomial complexities, Braided shuffle algebras and Lyndon words, Unnamed Item, A characterization of words of linear complexity, Reducing the ambiguity of Parikh matrices, Two-Dimensional Palindromes and Their Properties, Avoidability of long 𝑘-abelian repetitions, Substitutions and interval exchange transformations of rotation class, Nearly $k$-universal words -- investigating a part of Simon's congruence, Binary codes that do not preserve primitivity, Equations enforcing repetitions under permutations, Watson-Crick Conjugate and Commutative Words, Combinatorial View of Digital Convexity, Computing the $k$-binomial complexity of the Thue-Morse word, Generalized Lyndon factorizations of infinite words, Schwinger–Dyson operators as invariant vector fields on a matrix model analog of the group of loops, Reconstructing Words from Right-Bounded-Block Words