Weighted basic parallel processes
from commutative to noncommutative series
L. Clemente (University of Warsaw)
Highlights @ Bordeaux, September 2024
Motivation and context
Theory of power series in commuting variables Q[[x1, …, xd]]
Chomsky-like hierarchy
polynomials
rational
algebraic
D-finite�(holonomic)
D-algebraic
CDA
Typical questions
(+, *, derivation, inverse, composition, …)
Motivation and context
Theory of power series in commuting variables Q[[x1, …, xd]]
Chomsky-like hierarchy
polynomials
rational
algebraic
D-finite�(holonomic)
D-algebraic
CDA
Typical questions
(+, *, derivation, inverse, composition, …)
What is a good generalisation of power series in noncommuting variables?
Commuting → noncommuting variables
| commuting variables x, y, z | noncommuting variables a, b, c |
domain | power series | series over Σ := {a, b, c} |
notation | ℚ[[x, y, z]] := N³ → ℚ | ℚ《Σ》:= Σ* → ℚ |
| | |
| | |
| | |
Commuting → noncommuting variables
| commuting variables x, y, z | noncommuting variables a, b, c |
domain | power series | series over Σ := {a, b, c} |
notation | ℚ[[x, y, z]] := N³ → ℚ | ℚ《Σ》:= Σ* → ℚ |
sum | pointwise | pointwise |
| | |
| | |
Commuting → noncommuting variables
| commuting variables x, y, z | noncommuting variables a, b, c |
domain | power series | series over Σ := {a, b, c} |
notation | ℚ[[x, y, z]] := N³ → ℚ | ℚ《Σ》:= Σ* → ℚ |
sum | pointwise | pointwise |
product | high-school multiplication xy * z = xyz | |
| | |
Commuting → noncommuting variables
| commuting variables x, y, z | noncommuting variables a, b, c |
domain | power series | series over Σ := {a, b, c} |
notation | ℚ[[x, y, z]] := N³ → ℚ | ℚ《Σ》:= Σ* → ℚ |
sum | pointwise | pointwise |
product | high-school multiplication xy * z = xyz | shuffle product ab ⧢ c = cab +acb + abc |
| | |
Commuting → noncommuting variables
| commuting variables x, y, z | noncommuting variables a, b, c |
domain | power series | series over Σ := {a, b, c} |
notation | ℚ[[x, y, z]] := N³ → ℚ | ℚ《Σ》:= Σ* → ℚ |
sum | pointwise | pointwise |
product | high-school multiplication xy * z = xyz | shuffle product ab ⧢ c = cab +acb + abc |
derivation | high-school partial derivative 𝛛x(xy) = y | |
Commuting → noncommuting variables
| commuting variables x, y, z | noncommuting variables a, b, c |
domain | power series | series over Σ := {a, b, c} |
notation | ℚ[[x, y, z]] := N³ → ℚ | ℚ《Σ》:= Σ* → ℚ |
sum | pointwise | pointwise |
product | high-school multiplication xy * z = xyz | shuffle product ab ⧢ c = cab +acb + abc |
derivation | high-school partial derivative 𝛛x(xy) = y | left derivation δa(ab) = b, δa(c) = 0 |
Mantra:
Power series = Series which are commutative
xy
ab + ba
power series in
commuting variables
series in
noncommuting variables
isomorphism of differential rings
Mantra:
Power series = Series which are commutative
xy
ab + ba
power series in
commuting variables
series in
noncommuting variables
isomorphism of differential rings
xyz
xy
abc + … + cab
z
*
ab + ba
c
⧢
Mantra:
Power series = Series which are commutative
xy
ab + ba
power series in
commuting variables
series in
noncommuting variables
isomorphism of differential rings
xyz
xy
abc + … + cab
z
*
ab + ba
c
⧢
y
b
𝛛x
δa
ab + ba
xy
Mantra:
Power series = Series which are commutative
xy
ab + ba
power series in
commuting variables
series in
noncommuting variables
isomorphism of differential rings
xyz
xy
abc + … + cab
z
*
ab + ba
c
⧢
y
b
𝛛x
δa
ab + ba
xy
Gain: shuffle and left derivation are defined for all series in noncommuting variables
Conservative extension
X ⊆ ℚ[[x, y, z]]
X’ ⊆ ℚ《a, b, c》
The new series which are commutative coincide with X
Examples for X:
rational, algebraic, D-finite, differentially algebraic power series
class X ⊆ ℚ[[x, y, z]]
of power series in
commuting variables
Conservative extension
class X’ ⊆ ℚ《a, b, c》
of series in
noncommuting variables
class X ⊆ ℚ[[x, y, z]]
of power series in
commuting variables
X ⊆ ℚ[[x, y, z]]
X’ ⊆ ℚ《a, b, c》
The new series which are commutative coincide with X
Examples for X:
rational, algebraic, D-finite, differentially algebraic power series
Conservative extension
class X’ ⊆ ℚ《a, b, c》
of series in
noncommuting variables
class X ⊆ ℚ[[x, y, z]]
of power series in
commuting variables
X = X’ ∩ commutative series
X ⊆ ℚ[[x, y, z]]
X’ ⊆ ℚ《a, b, c》
The new series which are commutative coincide with X
Examples for X:
rational, algebraic, D-finite, differentially algebraic power series
Conservative extension
class X’ ⊆ ℚ《a, b, c》
of series in
noncommuting variables
class X ⊆ ℚ[[x, y, z]]
of power series in
commuting variables
X = X’ ∩ commutative series
X ⊆ ℚ[[x, y, z]]
X’ ⊆ ℚ《a, b, c》
The new series which are commutative coincide with X
Examples for X:
rational, algebraic, D-finite, differentially algebraic power series
Conservative extension
class X’ ⊆ ℚ《a, b, c》
of series in
noncommuting variables
class X ⊆ ℚ[[x, y, z]]
of power series in
commuting variables
X = X’ ∩ commutative series
X ⊆ ℚ[[x, y, z]]
X’ ⊆ ℚ《a, b, c》
The new series which are commutative coincide with X
Examples for X:
rational, algebraic, D-finite, differentially algebraic power series
This talk
X = CDA power series [1]
X’ = WBPP series [2]
[1] Bergeron, Reutenauer ”Combinatorial resolution of systems of differential equations […]”. European Journal of Combinatorics, 11(6):501–512, 1990.
[2] C. ”Weighted basic parallel processes and combinatorial enumeration”. CONCUR’24.
Contributions
WBPP equivalence in 2EXPSPACE via effective algebraic geometry
[multiplicity equivalence of species of structures]
Weighted basic parallel processes
Simultaneous generalisation of
Configurations are polynomials of nonterminals ℚ[X, Y, Z].
The transition function Δ maps nonterminals to configurations.
The semantics of a nonterminal is a series [[X]].
Weighted basic parallel processes
Example
Δa(X) := Y * Z
Δb(Y) := 1
Δb(Z) := 1
Simultaneous generalisation of
Configurations are polynomials of nonterminals ℚ[X, Y, Z].
The transition function Δ maps nonterminals to configurations.
The semantics of a nonterminal is a series [[X]].
Weighted basic parallel processes
Example
Δa(X) := Y * Z
Δb(Y) := 1
Δb(Z) := 1
Y*Z
X
a
WBPP run example
Simultaneous generalisation of
Configurations are polynomials of nonterminals ℚ[X, Y, Z].
The transition function Δ maps nonterminals to configurations.
The semantics of a nonterminal is a series [[X]].
Weighted basic parallel processes
Example
Δa(X) := Y * Z
Δb(Y) := 1
Δb(Z) := 1
Y*Z
X
Z+Y
a
b
WBPP run example
Leibniz rule from calculus
Δb(Y * Z) = Δb(Y) * Z + Y * Δb(Z)
Simultaneous generalisation of
Configurations are polynomials of nonterminals ℚ[X, Y, Z].
The transition function Δ maps nonterminals to configurations.
The semantics of a nonterminal is a series [[X]].
Weighted basic parallel processes
Example
Δa(X) := Y * Z
Δb(Y) := 1
Δb(Z) := 1
Linearity
Δb(Z + Y) = Δb(Z) + Δb(Y)
Y*Z
X
Z+Y
a
b
2
b
WBPP run example
Leibniz rule from calculus
Δb(Y * Z) = Δb(Y) * Z + Y * Δb(Z)
Simultaneous generalisation of
Configurations are polynomials of nonterminals ℚ[X, Y, Z].
The transition function Δ maps nonterminals to configurations.
The semantics of a nonterminal is a series [[X]].
Technical contribution
Equivalence problem [[X]] = [[Y]]?
Theorem. The equivalence problem for WBPP is in 2-EXPSPACE.
Technical contribution
Equivalence problem [[X]] = [[Y]]?
Theorem. The equivalence problem for WBPP is in 2-EXPSPACE.
Algorithm: Build a chain of polynomial ideals of configurations.
Termination: Hilbert’s finite basis theorem.
Technical contribution
Equivalence problem [[X]] = [[Y]]?
Theorem. The equivalence problem for WBPP is in 2-EXPSPACE.
Algorithm: Build a chain of polynomial ideals of configurations.
Termination: Hilbert’s finite basis theorem.
Complexity: Effective bounds from algebraic geometry.
Theorem 4 of [1]. When Σ = {a}, the length of the chain is 2-EXP.
[1] Novikov, Yakovenko “Trajectories of polynomial vector fields […]”, Annales de l’Institut Fourier, 49(2):563–609, 1999.
Note: [1] is about dynamical systems but its techniques apply to WBPP.
Technical contribution
Equivalence problem [[X]] = [[Y]]?
Theorem. The equivalence problem for WBPP is in 2-EXPSPACE.
Algorithm: Build a chain of polynomial ideals of configurations.
Termination: Hilbert’s finite basis theorem.
Complexity: Effective bounds from algebraic geometry.
Theorem 4 of [1]. When Σ = {a}, the length of the chain is 2-EXP.
[1] Novikov, Yakovenko “Trajectories of polynomial vector fields […]”, Annales de l’Institut Fourier, 49(2):563–609, 1999.
Theorem. The same for arbitrary Σ.
Note: [1] is about dynamical systems but its techniques apply to WBPP.
Note: Elementary bounds on polynomial ideals are rare.
Technical contribution
Equivalence problem [[X]] = [[Y]]?
Theorem. The equivalence problem for WBPP is in 2-EXPSPACE.
Algorithm: Build a chain of polynomial ideals of configurations.
Termination: Hilbert’s finite basis theorem.
Complexity: Effective bounds from algebraic geometry.
Theorem 4 of [1]. When Σ = {a}, the length of the chain is 2-EXP.
[1] Novikov, Yakovenko “Trajectories of polynomial vector fields […]”, Annales de l’Institut Fourier, 49(2):563–609, 1999.
Theorem. The same for arbitrary Σ.
Note: [1] is about dynamical systems but its techniques apply to WBPP.
Note: Elementary bounds on polynomial ideals are rare.
more details on the poster