International Journal of Algebra and Computation

This paper deals with balances and imbalances in Arnoux–Rauzy words. We provide sufficient conditions for C-balancedness, but our results indicate that even a characterization of 2-balanced Arnoux–Rauzy words on a 3-letter alphabet is not immediate.

We prove that the Fibonacci word f satisfies among all characteristic Sturmian words, three interesting extremal properties. The first concerns the length and the second the minimal period of its palindromic prefixes. Each of these two properties characterizes f up to a renaming of its letters. A third property concerns the number of occurrences of the letter b in its palindromic prefixes. It characterizes uniquely f among all characteristic Sturmian words having the prefix abaa.

Given a cluster-tilted algebra B we study its first Hochschild cohomology group HH¹(B) with coefficients in the B–B-bimodule B. If C is a tilted algebra such that B is the relation extension of C by , then we prove that HH¹(B) is isomorphic, as a vector space, to the direct sum of HH¹(C) with HH¹(B,E). This yields homological interpretations for results of the first and the fourth authors with M. J. Redondo.

The associahedron is an object that has been well studied and has numerous applications, particularly in the theory of operads, the study of non-crossing partitions, lattice theory and more recently in the study of cluster algebras. We approach the associahedron from the point of view of discrete homotopy theory. We study the abelianization of the discrete fundamental group, and show that it is free abelian of rank . We also find a combinatorial description for a basis of this rank. We also introduce the exchange module of the type A_n cluster algebra, used to model the relations in the cluster algebra. We use the discrete fundamental group to the study of exchange module, and show that it is also free abelian of rank .

We give an LU-decomposition of the supercharacter table of the group of n × n unipotent upper triangular matrices over 𝔽_q, into a lower-triangular matrix with entries in ℤ[q] and an upper-triangular matrix with entries in ℤ[q^-1]. To this end, we introduce a q deformation of a new power-sum basis of the Hopf algebra of symmetric functions in noncommuting variables. The decomposition is obtained from the transition matrices between the supercharacter basis, the q-power-sum basis and the superclass basis. This is similar to the decomposition of the character table of the symmetric group S_n given by the transition matrices between Schur functions, monomials and power-sums. We deduce some combinatorial results associated to this decomposition. In particular, we compute the determinant of the supercharacter table.

We investigate the connections between various noncommutative analogues of Hall–Littlewood and Macdonald polynomials, and define some new families of noncommutative symmetric functions depending on two sequences of parameters.

We give a polynomial basis of each irreducible representation of the Hecke algebra, as well as an adjoint basis. Decompositions in these bases are obtained by mere specializations.

We construct an action of the braid group B_2g+2 on the free group F_2g extending an action of B₄ on F₂ introduced earlier by Reutenauer and the author. Our action induces a homomorphism from B_2g+2 into the symplectic modular group Sp_2g(ℤ). In the special case g = 2 we show that the latter homomorphism is surjective and determine its kernel, thus obtaining a braid-like presentation of Sp₄(ℤ).

The aim of this work is to describe new explicit recursive formulas for (renormalized) Macdonald polynomials, using Pieri-like formulas.

We study the internal structure of enveloping algebras of preLie algebras. We show in particular that the canonical projections arising from the Poincaré–Birkhoff–Witt theorem can be computed explicitly. They happen to be closely related to the Magnus formula for matrix differential equations. Indeed, we show that the Magnus formula provides a way to compute the canonical projection on the preLie algebra. Conversely, our results provide new insights on classical problems in the theory of differential equations and on recent advances in their combinatorial understanding.

This paper addresses the problem of the validity of weighted automata in which the presence of ε-circuits results in infinite summations. Earlier works either rule out such automata or characterize the semirings in which these infinite sums are all well-defined.

By means of a topological approach, we take here a definition of validity that is strong enough to insure that in any kind of semirings, any closure algorithm will succeed on every valid weighted automaton and turn it into an equivalent proper automaton. This definition is stable with respect to natural transformations of automata.

The classical closure algorithms, in particular algorithms based on the computation of the star of the matrix of ε-transitions, cannot be used to decide validity. This decision problem remains open for general topological semirings.

We present a closure algorithm that yields a decision procedure for the validity of automata in the case where the weights are taken in ℚ or ℝ, two cases that had never been treated before. These algorithm and procedure are implemented in the VAUCANSON platform.

We study the family of rational sets of words, called completely reducible and which are such that the syntactic representation of their characteristic series is completely reducible. This family contains, by a result of Reutenauer, the submonoids generated by bifix codes and, by a result of Berstel and Reutenauer, the cyclic sets. We study the closure properties of this family. We prove a result on linear representations of monoids which gives a generalization of the result concerning the complete reducibility of the submonoid generated by a bifix code to sets called birecurrent. We also give a new proof of the result concerning cyclic sets.

We discuss some combinatorial and algebraic problems which have arisen from the study of the nonlinear Schrödinger equation. In particular we discuss a combinatorial graph, which we call energy graph associated to a Cayley graph. Some important features of normal forms are hidden into properties of this graph. Some of these properties are at the moment only conjectural and we point out the state of the art.

Motivated by the extension of the critical factorization theorem to infinite words, we study the (local) periodicity function, i.e. the function that, for any position in a word, gives the size of the shortest square centered in that position. We prove that this function characterizes any binary word up to exchange of letters. We then introduce a new complexity function for words (the periodicity complexity) that, for any position in the word, gives the average value of the periodicity function up to that position. The new complexity function is independent from the other commonly used complexity measures as, for instance, the factor complexity. Indeed, whereas any infinite word with bounded factor complexity is periodic, we will show a recurrent non-periodic word with bounded periodicity complexity. Further, we will prove that the periodicity complexity function grows as Θ(log n) in the case of the Fibonacci infinite word and that it grows as Θ(n) in the case of the Thue–Morse word. Finally, we will show examples of infinite recurrent words with arbitrary high periodicity complexity.

We show that there exist two natural endomorphism algebras for shuffle bialgebras such as Sh(X), where X is a graded set. One of these endomorphism algebras is a natural extension of the Malvenuto–Reutenauer Hopf algebra and is defined using graded permutations. The other one, the dendriform descent algebra, is a subalgebra of the first defined by mimicking the definition of the descent algebras by convolution from the graded projections in the tensor algebra. We study these algebras for their own, show that they carry bidendriform structures and establish freeness properties, study their generators, dimensions, bases, and also feature their relations to the internal structure of shuffle algebras. As an application of these ideas, we give a new proof of Chapoton's rigidity theorem for shuffle bialgebras.