You are not logged in |
The commutativity problem for varieties of formal series and applications
- Speaker(s)
- Lorenzo Clemente
- Affiliation
- University of Warsaw
- Language of the talk
- English
- Date
- Dec. 18, 2024, 2:15 p.m.
- Room
- room 5440
- Title in Polish
- The commutativity problem for varieties of formal series and applications
- Seminar
- Seminar Automata Theory
Let Σ be a finite alphabet of noncommuting indeterminates.
A *formal series* over the rational numbers is a mapping Σ* → ℚ.
We say that it is *commutative* if the output does not depend on the order of the symbols in the input.
Commutative series provide a bridge between the world of formal series in noncommuting variables,
commonly arising in theoretical computer science (e.g., weighted automata),
and the world of formal power series in commuting variables,
commonly arising in mathematics (e.g., generating functions from combinatorics).
The *commutativity problem* for a class of series amounts to establishing whether a given series from the class is commutative.
This is a fundamental decision problem which does not seem to have been posed before.
Our first result is that this problem is decidable for effective *prevarieties of formal series*, a notion introduced by Reutenauer in 1980.
In order to apply this result, we show that several commonly occurring classes of formal series are indeed effective prevarieties.
Examples include the rational series, for which the result can be regarded as folklore,
but also novel classes such as *polynomial automata* series, and the recently introduced *shuffle-finite series*.
This provides further evidence of the robustness of these classes.
We conclude by applying our results to solvability of systems of nonlinear multivariate difference and differential equations.
While such systems are known to be undecidable in full generality,
we show that decidability is regained for natural subclasses by reducing to commutativity over suitable prevarieties of formal series.
Let Σ be a finite alphabet of noncommuting indeterminates.
A *formal series* over the rational numbers is a mapping Σ* → ℚ.
We say that it is *commutative* if the output does not depend on the order of the symbols in the input.
Commutative series provide a bridge between the world of formal series in noncommuting variables,
commonly arising in theoretical computer science (e.g., weighted automata),
and the world of formal power series in commuting variables,
commonly arising in mathematics (e.g., generating functions from combinatorics).
The *commutativity problem* for a class of series amounts to establishing whether a given series from the class is commutative.
This is a fundamental decision problem which does not seem to have been posed before.
Our first result is that this problem is decidable for effective *prevarieties of formal series*, a notion introduced by Reutenauer in 1980.
In order to apply this result, we show that several commonly occurring classes of formal series are indeed effective prevarieties.
Examples include the rational series, for which the result can be regarded as folklore,
but also novel classes such as *polynomial automata* series, and the recently introduced *shuffle-finite series*.
This provides further evidence of the robustness of these classes.
We conclude by applying our results to solvability of systems of nonlinear multivariate difference and differential equations.
While such systems are known to be undecidable in full generality,
we show that decidability is regained for natural subclasses by reducing to commutativity over suitable prevarieties of formal series.
