This repository contains the literate Agda formalisation for the paper "Commutative algebras of series" by Lorenzo Clemente (LICS’26). Background, motivation, and examples are given in the paper, which contains clickable links to the relevant parts of this website. We develop a fragment of the theory of formal series in noncommuting variables and their algebraic properties. Our approach is coinductive, using Agda’s sized types and guardedness features.
This website is meant to be accessible without referring to the paper. In particular, it can be used as a tutorial on the formalisation of power series in Agda. Clicking on a keyword will take you to its definition.
We quote below the abstract from the paper.
We consider a large family of product operations of formal power series in noncommuting indeterminates, the classes of automata they define, and the respective equivalence problems. A P-product of series is defined coinductively by a polynomial product rule P, which gives a recursive recipe to build the product of two series as a function of the series themselves and their derivatives. The first main result of the paper is a complete and decidable characterisation of all product rules P giving rise to P-products which are bilinear, associative, and commutative (BAC). The characterisation shows that there are infinitely many such products, and in particular it applies to the notable Hadamard, shuffle, and infiltration products from the literature. Every P-product gives rise to the class of P-automata, an infinite-state model where states are terms. The second main result of the paper is that the equivalence problem for P-automata is decidable for P-products satisfying our characterisation. This explains, subsumes, and extends known results about the Hadamard, shuffle, and infiltration automata.