Commutative algebras of series
For researchers in automata theory and formal power series, this provides a unified framework and decidability results for a broad family of products and automata.
This paper characterizes all bilinear, associative, and commutative product operations on formal power series defined by polynomial product rules, showing there are infinitely many such products. It also proves that the equivalence problem for automata corresponding to these products is decidable, subsuming and extending previous results for Hadamard, shuffle, and infiltration automata.
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. 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 previous results on Hadamard, shuffle, and infiltration automata. We have formalised most results in the proof assistant Agda.