Commutative algebras of series

based on this paper (accepted at LICS’26)

Lorenzo Clemente

University of Warsaw

​

AAA109―SAL2026 @ Ljubljana, 07/06/2026

Placement

Application of coalgebra

to derive algebraic

and algorithmic results

Placement

Application of coalgebra

to derive algebraic

and algorithmic results

What is a series?

Fix a finite alphabet Σ = {a, b}

of noncommuting indeterminates.�

A series is a mapping f : Σ* → ℚ�(sometimes written ℚ⟪a, b⟫)

Vector space structure

Series f, g : ℚ《Σ》

​

• Scalar multiplication:

(c · f)(w) := c · f(w) for all c ∈ ℚ, w ∈ Σ*

​

• Addition:

(f + g)(w) := f(w) + g(w) for all w ∈ Σ*

​

​

​

​

vector space

(ℚ⟪Σ⟫; 0, ·, +)

Transition structure

For an input symbol a ∈ Σ and a series f : ℚ⟪Σ⟫

let the left derivative by a be the series a⁻¹f : ℚ⟪Σ⟫ s.t.

​

(a⁻¹f)(w) = f(a·w), ∀ w ∈ Σ*

​

The left derivative operators (a^-1)_{a ∈ Σ} endow the set of series�with the structure of an (infinite) automaton (= coalgebra)

​

​

​

transition structure

(ℚ⟪Σ⟫; (a^-1)_{a ∈ Σ})

Transition structure

For an input symbol a ∈ Σ and a series f : ℚ⟪Σ⟫

let the left derivative by a be the series a⁻¹f : ℚ⟪Σ⟫ s.t.

​

(a⁻¹f)(w) = f(a·w), ∀ w ∈ Σ*

​

The left derivative operators (a^-1)_{a ∈ Σ} endow the set of series�with the structure of an (infinite) automaton (= coalgebra)

​

​

​

transition structure / automaton / coalgebra

(ℚ⟪Σ⟫; (a^-1)_{a ∈ Σ})

The big picture

The big picture

The big picture

The big picture

(D)

zeroness problem

The big picture

(D)

zeroness problem

is a given a rational series / weighted automaton zero?

(= word problem for algebras)

The big picture

(D)

zeroness problem

Theorem�(Schützenberger 1960’s).�Zeroness of rational series / weighted automata is decidable.

is a given a rational series / weighted automaton zero?

(= word problem for algebras)

The big picture

Theorem�(Schützenberger 1960’s).�Zeroness of rational series / weighted automata is decidable.

is a given a rational series / weighted automaton zero?

(= word problem for algebras)

The big picture

The big picture

The big picture

The big picture

Hadamard and shuffle in TCS

Hadamard product

vector space

rational series

weighted automata

linear algebra

Hadamard product

vector space

rational series

weighted automata

linear algebra

Theorem [1].�Zeroness of Hadamard-finite series / Hadamard automata is decidable.

​

[1] Benedikt, Duff, Sharad, Worrell “Polynomial automata: Zeroness and applications” (LICS 2017)

Shuffle product

vector space

rational series

weighted automata

linear algebra

Shuffle product

vector space

rational series

weighted automata

linear algebra

Theorem [1].�Zeroness of shuffle-finite series / shuffle automata is decidable.

​

[1] C “Weighted basic parallel processes and combinatorial enumeration” (CONCUR 2024)

Infiltration product

Infiltration product

Infiltration product

vector space

rational series

weighted automata

linear algebra

Infiltration product

vector space

rational series

weighted automata

linear algebra

Theorem [1].�Zeroness of infiltration-finite series / infiltration automata is decidable.

​

[1] C “The commutativity problem for effective varieties of formal series, and applications” (LICS 2025)

The big picture

The big picture

Goal

Which product operations “ * ”�give rise to a decidable zeroness problem?

Commonalities

The Hadamard, shuffle, and infiltration product are�

• bilinear, associative, and commutative�
• they satisfy product rules!

​

​

Commonalities

The Hadamard, shuffle, and infiltration product are�

• bilinear, associative, and commutative�
• they satisfy product rules!

​

​

Product rules

Consider polynomials of the form P(x, ẋ, y, ẏ) ∈ ℚ[x, ẋ, y, ẏ].�A P-product is a binary operation on sequences “∗” s.t.

​

a^-1 (f ∗ g) = P(f, a^-1 f, g, a^-1 g), ∀ a ∈ Σ

Product rules

Consider polynomials of the form P(x, ẋ, y, ẏ) ∈ ℚ[x, ẋ, y, ẏ].�A P-product is a binary operation on sequences “∗” s.t.

​

a^-1 (f ∗ g) = P(f, a^-1 f, g, a^-1 g), ∀ a ∈ Σ

Product rules

Consider polynomials of the form P(x, ẋ, y, ẏ) ∈ ℚ[x, ẋ, y, ẏ].�A P-product is a binary operation on sequences “∗” s.t.

​

a^-1 (f ∗ g) = P(f, a^-1 f, g, a^-1 g), ∀ a ∈ Σ

Product rules

Consider polynomials of the form P(x, ẋ, y, ẏ) ∈ ℚ[x, ẋ, y, ẏ].�A P-product is a binary operation on sequences “∗” s.t.

​

a^-1 (f ∗ g) = P(f, a^-1 f, g, a^-1 g), ∀ a ∈ Σ

Product rules

Consider polynomials of the form P(x, ẋ, y, ẏ) ∈ ℚ[x, ẋ, y, ẏ].�A P-product is a binary operation on sequences “∗” s.t.

​

a^-1 (f ∗ g) = P(f, a^-1 f, g, a^-1 g), ∀ a ∈ Σ

Product rules

(CONCUR 2021)

Product rules

(CONCUR 2021)

Can we understand whether a P-product is BAC,�

• Bilinear
• Associative
• Commutative,�

just by looking at its product rule P?

BAC (non-)examples

BAC (non-)examples

BAC (non-)examples

BAC (non-)examples

BAC (non-)examples

BAC (non-)examples

BAC (non-)examples

BAC classification

​

A P-product is a binary operation on series “∗” s.t.

a^-1 (f ∗ g) = P(f, a^-1 f, g, a^-1 g), ∀ a ∈ Σ

​

A product rule P is simple if there are constants α, β, γ ∈ ℚ:

​

P(x, ẋ, y, ẏ) = α · xy + β · (ẋy + xẏ) + γ · ẋẏ

s.t. α γ = β (β - 1)

​

​

​

​

​

​

Theorem. A P-product is BAC iff P is simple.

Proof. Apply the previous characterisation.

BAC classification

​

A P-product is a binary operation on series “∗” s.t.

a^-1 (f ∗ g) = P(f, a^-1 f, g, a^-1 g), ∀ a ∈ Σ

​

A product rule P is simple if there are constants α, β, γ ∈ ℚ:

​

P(x, ẋ, y, ẏ) = α · xy + β · (ẋy + xẏ) + γ · ẋẏ

s.t. α γ = β (β - 1)

​

​

​

​

​

​

Theorem. A P-product is BAC iff P is simple.

Proof. By coinduction.

BAC classification

​

A P-product is a binary operation on series “∗” s.t.

a^-1 (f ∗ g) = P(f, a^-1 f, g, a^-1 g), ∀ a ∈ Σ

​

A product rule P is simple if there are constants α, β, γ ∈ ℚ:

​

P(x, ẋ, y, ẏ) = α · xy + β · (ẋy + xẏ) + γ · ẋẏ

s.t. α γ = β (β - 1)

​

​

​

​

​

​

Theorem. A P-product is BAC iff P is simple.

Proof. By coinduction.

And concatenation?

Let ∗ be the concatenation (Cauchy) product.

​

• bilinear ✓
• associative ✓
• non-commutative ❌

​

Brzozowski’s product rule

a^-1 (f ∗ g) = (a^-1 f) ∗ g + f(0) · (a^-1 g) NOT a P-product! (for any P)

And concatenation?

Let ∗ be the concatenation (Cauchy) product.

​

• bilinear ✓
• associative ✓
• non-commutative ❌

​

Brzozowski’s product rule

a^-1 (f ∗ g) = (a^-1 f) ∗ g + f(0) · (a^-1 g) NOT a P-product! (for any P)

The big picture

Rational series

A series f is rational if it belongs to a finite-dimensional vector space

closed under the left derivative operators (a^-1)_{a ∈ Σ}.

​

Equivalently, there are generators g₁ = f, …, g_k s.t.

for every generator g_i and input symbol a ∈ Σ,

​

a^-1 g_i is a linear combination over ℚ of g₁, …, g_k

​

​

Rational series

A series f is rational if it belongs to a finite-dimensional vector space

closed under the left derivative operators (a^-1)_{a ∈ Σ}.

​

Equivalently, there are generators g₁ = f, …, g_k s.t.

for every generator g_i and input symbol a ∈ Σ,

​

a^-1 g_i is a linear combination over ℚ of g₁, …, g_k

​

​

Rational series

Berstel, Reutenauer:�Noncommutative rational series with applications

(2010)

Rational series

A series f is rational if it belongs to a finite-dimensional vector space

closed under the left derivative operators (a^-1)_{a ∈ Σ}.

​

Equivalently, there are generators g₁ = f, …, g_k s.t.

for every generator g_i and input symbol a ∈ Σ,

​

a^-1 g_i is a linear combination over ℚ of g₁, …, g_k

​

​

Rational → P-finite series

A series f is rational if it belongs to a finite-dimensional vector space

closed under the left derivative operators (a^-1)_{a ∈ Σ}.

​

Equivalently, there are generators g₁ = f, …, g_k s.t.

for every generator g_i and input symbol a ∈ Σ,

​

a^-1 g_i is a linear combination over ℚ of g₁, …, g_k

​

​

P-finite

algebra

polynomial

Rational → P-finite series

A series f is rational if it belongs to a finite-dimensional vector space

closed under the left derivative operators (a^-1)_{a ∈ Σ}.

​

Equivalently, there are generators g₁ = f, …, g_k s.t.

for every generator g_i and input symbol a ∈ Σ,

​

a^-1 g_i is a linear combination over ℚ of g₁, …, g_k

​

​

P-finite

algebra

Rational → P-finite series

A series f is rational if it belongs to a finite-dimensional vector space

closed under the left derivative operators (a^-1)_{a ∈ Σ}.

​

Equivalently, there are generators g₁ = f, …, g_k s.t.

for every generator g_i and input symbol a ∈ Σ,

​

a^-1 g_i is a linear combination over ℚ of g₁, …, g_k

​

​

P-finite

algebra

polynomial

Examples

Take Σ = { a }.

Consider the Hadamard product rule P = ẋẏ.�

The series f = aⁿ ↦ 2^(2ⁿ) is P-finite (= Hadamard finite) since�

a^-1 f = f ⊙ f

Examples

Take Σ = { a }.

Consider the shuffle product rule P = ẋy + xẏ.�

The series f = aⁿ ↦ n! is P-finite (= shuffle finite) since

a^-1 f = f ш f

Sanity check

Lemma. Fix a product rule P.

The class of P-finite series is an algebra closed under left derivatives (a^-1)_{a ∈ Σ}.

The big picture

P-automata

Consider a product rule P ∈ ℚ[x, ẋ, y, ẏ].

A P-automaton is a tuple

​

A = (Σ, X, F, Δ), where

​

• X = {x₁, …, xₖ} is a finite set of commuting variables
• F : X → ℚ is the output function
• Δ : Σ → X → ℚ[X] is the transition function

​

A P-automaton starting from configuration p ∈ ℚ[X] recognises a series

A⟦ p ⟧ : ℚ《Σ》

P-automata

Consider a product rule P ∈ ℚ[x, ẋ, y, ẏ].

A P-automaton is a tuple

​

A = (Σ, X, F, Δ), where

​

• X = {x₁, …, xₖ} is a finite set of commuting variables
• F : X → ℚ is the output function
• Δ : Σ → X → ℚ[X] is the transition function

​

A P-automaton starting from configuration p ∈ ℚ[X] recognises a series

A⟦ p ⟧ : ℚ《Σ》

Shuffle automaton example

Fix the shuffle product rule P = ẋy + xẏ.

Consider the P-automaton A = (Σ = { a }, X = { x }, F : X → ℚ, Δ : X → ℚ[X]):

​

• The output function is F x = 1.
• The transition function is Δ x = x².

​

It recognises the series A⟦x⟧ = aⁿ ↦ n!

​

x

Shuffle automaton example

Fix the shuffle product rule P = ẋy + xẏ.

Consider the P-automaton A = (Σ = { a }, X = { x }, F : X → ℚ, Δ : X → ℚ[X]):

​

• The output function is F x = 1.
• The transition function is Δ x = x².

​

It recognises the series A⟦x⟧ = aⁿ ↦ n!

​

x

↓F

A⟦x⟧ = 1

Shuffle automaton example

Fix the shuffle product rule P = ẋy + xẏ.

Consider the P-automaton A = (Σ = { a }, X = { x }, F : X → ℚ, Δ : X → ℚ[X]):

​

• The output function is F x = 1.
• The transition function is Δ x = x².

​

It recognises the series A⟦x⟧ = aⁿ ↦ n!

​

x ―Δ—> x²

↓F

A⟦x⟧ = 1

Shuffle automaton example

Fix the shuffle product rule P = ẋy + xẏ.

Consider the P-automaton A = (Σ = { a }, X = { x }, F : X → ℚ, Δ : X → ℚ[X]):

​

• The output function is F x = 1.
• The transition function is Δ x = x².

​

It recognises the series A⟦x⟧ = aⁿ ↦ n!

​

x ―Δ—> x²

↓F ↓F

A⟦x⟧ = 1 1

Shuffle automaton example

Fix the shuffle product rule P = ẋy + xẏ.

Consider the P-automaton A = (Σ = { a }, X = { x }, F : X → ℚ, Δ : X → ℚ[X]):

​

• The output function is F x = 1.
• The transition function is Δ x = x².

​

It recognises the series A⟦x⟧ = aⁿ ↦ n!

​

x ―Δ—> x² ―Δ—> ???

↓F ↓F

A⟦x⟧ = 1 1

Shuffle automaton example

Fix the shuffle product rule P = ẋy + xẏ.

Consider the P-automaton A = (Σ = { a }, X = { x }, F : X → ℚ, Δ : X → ℚ[X]),

​

• The output function is F x = 1.
• The transition function is Δ x = x².

​

It recognises the series A⟦x⟧ = aⁿ ↦ n!

​

x ―Δ—> x² ―Δ—> ???

↓F ↓F

A⟦x⟧ = 1 1

Extension Lemma 1. Every Δ : X → ℚ[x] extends (uniquely) to a linear function�Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · q + p · (Δq)

(derivation)

​

Example: Δ(xⁿ) = n · xⁿ⁻¹ · (Δ x)

Shuffle automaton example

Fix the shuffle product rule P = ẋy + xẏ.

Consider the P-automaton A = (Σ = { a }, X = { x }, F : X → ℚ, Δ : X → ℚ[X]),

​

• The output function is F x = 1.
• The transition function is Δ x = x².

​

It recognises the series A⟦x⟧ = aⁿ ↦ n!

​

x ―Δ—> x² ―Δ—> 2x³ ―Δ—> 6x⁴ ―Δ—> … ―Δ—> n! xⁿ⁺¹

↓F ↓F ↓F ↓F ↓F

A⟦x⟧ = 1 1 2 6 … n!

Extension Lemma 1. Every Δ : X → ℚ[x] extends (uniquely) to a linear function�Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · q + p · (Δq)

(derivation)

​

Example: Δ(xⁿ) = n · xⁿ⁻¹ · (Δ x)

Extension lemmas

Extension Lemma 3. Every Δ : X → ℚ[x] extends (uniquely) to a linear function Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · q + p · (Δq) + (Δp) · (Δq) infiltration product rule

Extension Lemma 2. Every Δ : X → ℚ[x] extends (uniquely) to a linear function Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · (Δq) Hadamard product rule

Extension Lemma 1. Every Δ : X → ℚ[x] extends (uniquely) to a linear function Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · q + p · (Δq) shuffle product rule

Extension lemmas

Extension Lemma 3. Every Δ : X → ℚ[x] extends (uniquely) to a linear function Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · q + p · (Δq) + (Δp) · (Δq) infiltration product rule

Extension Lemma 2. Every Δ : X → ℚ[x] extends (uniquely) to a linear function Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · (Δq) Hadamard product rule

Extension Lemma 1. Every Δ : X → ℚ[x] extends (uniquely) to a linear function Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · q + p · (Δq) shuffle product rule

Extension lemmas

Extension Lemma 3. Every Δ : X → ℚ[x] extends (uniquely) to a linear function Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · q + p · (Δq) + (Δp) · (Δq) infiltration product rule

Extension Lemma 2. Every Δ : X → ℚ[x] extends (uniquely) to a linear function Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · (Δq) Hadamard product rule

Extension Lemma 1. Every Δ : X → ℚ[x] extends (uniquely) to a linear function Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · q + p · (Δq) shuffle product rule

Extension lemmas

Extension Lemma 3. Every Δ : X → ℚ[x] extends (uniquely) to a linear function Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · q + p · (Δq) + (Δp) · (Δq) infiltration product rule

Extension Lemma 2. Every Δ : X → ℚ[x] extends (uniquely) to a linear function Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · (Δq) Hadamard product rule

Extension Lemma 1. Every Δ : X → ℚ[x] extends (uniquely) to a linear function Δ : ℚ[x] → ℚ[x] s.t.

​

Δ (pq) = (Δp) · q + p · (Δq) shuffle product rule

Can we characterise which product rules give rise to a corresponding Extension Lemma?

P-functions

Consider a product rule P ∈ ℚ[x, ẋ, y, ẏ].

Δ : ℚ[X] → ℚ[X] is a P-function if it is linear and it satisfies the product rule�

Δ (p q) = P(p, Δ p, q, Δ q)

​

Extension Lemma*.

Let P be a BAC product rule.�Every function Δ : X → ℚ[X] extends (uniquely) to a P-function ℚ[X] → ℚ[X].

* Conditions apply: Since we do not require the series product to have an identity we need to restrict to polynomials without constant term

P-functions

Consider a product rule P ∈ ℚ[x, ẋ, y, ẏ].

Δ : ℚ[X] → ℚ[X] is a P-function if it is linear and it satisfies the product rule�

Δ (p q) = P(p, Δ p, q, Δ q)

​

Extension Lemma*.

Let P be a BAC product rule.�Every function Δ : X → ℚ[X] extends (uniquely) to a P-function ℚ[X] → ℚ[X].

* Conditions apply: Since we do not require the series product to have an identity we need to restrict to polynomials without constant term

P-automata: Semantics

Fix A = (Σ, X, F, Δ) and p ∈ ℚ[X]. We define the semantics A⟦ p ⟧ : ℚ《Σ》

p

Δ_ap

Δ_bΔ_ap

…

Δ_wp

output

A⟦p⟧(w) := F (Δ_w p)

F

a

b

P-automata: Semantics

Fix A = (Σ, X, F, Δ) and p ∈ ℚ[X]. We define the semantics A⟦ p ⟧ : ℚ《Σ》

Δ : X → ℚ[X]

p

Δ_ap

Δ_bΔ_ap

…

Δ_wp

output

A⟦p⟧(w) := F (Δ_w p)

F

a

b

P-automata: Semantics

Δ : Σ → ℚ[X] → ℚ[X]

Fix A = (Σ, X, F, Δ) and p ∈ ℚ[X]. We define the semantics A⟦ p ⟧ : ℚ《Σ》

Δ : Σ → X → ℚ[X]

by the Extension Lemma,�extend to a unique P-function

Δ_a(pq) = P(p, Δ_ap, q, Δ_aq)

p

Δ_ap

Δ_bΔ_ap

…

Δ_wp

output

A⟦p⟧(w) := F (Δ_w p)

F

a

b

P-automata: Semantics

Δ : Σ* → ℚ[X] → ℚ[X]

Δ : Σ → ℚ[X] → ℚ[X]

Fix A = (Σ, X, F, Δ) and p ∈ ℚ[X]. We define the semantics A⟦ p ⟧ : ℚ《Σ》

Δ : Σ → X → ℚ[X]

by the Extension Lemma,�extend to a unique P-function

Δ_a(pq) = P(p, Δ_ap, q, Δ_aq)

extend�homomorphically

Δ_ε p = p

Δ_{a · w} p = Δ_w (Δ_a p)

p

Δ_ap

Δ_bΔ_ap

…

Δ_wp

output

A⟦p⟧(w) := F (Δ_w p)

F

a

b

P-automata: Semantics

Δ : Σ* → ℚ[X] → ℚ[X]

Δ : Σ → ℚ[X] → ℚ[X]

Fix A = (Σ, X, F, Δ) and p ∈ ℚ[X]. We define the semantics A⟦ p ⟧ : ℚ《Σ》

extend�homomorphically

Δ_ε p = p

Δ_{a · w} p = Δ_w (Δ_a p)

p

Δ_ap

Δ_bΔ_ap

…

Δ_wp

output

A⟦p⟧(w) := F (Δ_w p)

F

a

b

Δ : Σ → X → ℚ[X]

by the Extension Lemma,�extend to a unique P-function

Δ_a(pq) = P(p, Δ_ap, q, Δ_aq)

SUMMARY

SUMMARY

Coincidence Lemma.

P-finite = P-automata

SUMMARY

Coincidence Lemma.

P-finite = P-automata

Theorem. Let P be a simple product rule. The zeroness problem is decidable for P-finite series / series recognised by P-automata.

Proof. Effective version of Hilbert’s finite basis theorem

End of the world