Journal article · 2026 · Open access
The commutativity problem for effective varieties of formal series, and applications
Journal of the ACM · Published 9 November 2026 · DOI 10.1145/3862472
In brief
“The commutativity problem for effective varieties of formal series, and applications” is a 2026 journal article by Lorenzo Clemente, published in Journal of the ACM. OpenAlex counts 0 citations as of 18 November 2026. It is open access under a CC BY licence: the full text is free to read at Journal of the ACM.
- Citations
- 0
- References
- 66
- Authors
- 1
Abstract
A formal series in noncommuting variables Σ over the rationals is a mapping \(\Sigma ^* \rightarrow {\mathbb {Q}} \) from the free monoid generated by Σ to the rationals. We say that it is commutative if the output does not depend on the order of the symbols in the input. The commutativity problem for a class of series takes as input a (finite presentation of) a series from the class and amounts to establishing whether it is commutative. This is a very natural, albeit nontrivial problem, which has not been considered before from an algorithmic perspective. We show that commutativity is decidable for all classes of series that constitute a so-called effective prevariety , a notion generalising Reutenauer’s varieties of formal series. For example, the class of rational series , introduced by Schützenberger in the 1960’s, is well-known to be an effective (pre)variety, and thus commutativity is decidable for it. In order to showcase the applicability of our result, we consider classes of formal series generalising the rational ones. We consider polynomial automata , shuffle automata , and infiltration automata , and we show that each of these models recognises an effective prevariety of formal series. Consequently, their commutativity problem is decidable, which is a novel result. We find it remarkable that commutativity can be decided in a uniform way for such disparate computation models. Finally, we present applications of commutativity outside the theory of formal series. We show that we can decide solvability in sequences and in power series for restricted classes of algebraic difference and differential equations, for which such problems are undecidable in full generality. Thanks to this, we can prove that the syntaxes of multivariate polynomial recursive sequences and of constructible differentially algebraic power series are effective, which are new results about problems left open in previous work.
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Clemente, L. (2026). The commutativity problem for effective varieties of formal series, and applications. Journal of the ACM. https://doi.org/10.1145/3862472
MLA 9
Clemente, Lorenzo. “The commutativity problem for effective varieties of formal series, and applications.” Journal of the ACM, 2026. https://doi.org/10.1145/3862472.
Chicago
Clemente, Lorenzo. 2026. “The commutativity problem for effective varieties of formal series, and applications.” Journal of the ACM. https://doi.org/10.1145/3862472.
Harvard
Clemente, L. (2026) ‘The commutativity problem for effective varieties of formal series, and applications’, Journal of the ACM. doi:10.1145/3862472.
IEEE
L. Clemente, “The commutativity problem for effective varieties of formal series, and applications,” Journal of the ACM, 2026, doi: 10.1145/3862472.
BibTeX
@article{clemente2026commutativity,
title = {{The commutativity problem for effective varieties of formal series, and applications}},
author = {Clemente, Lorenzo},
journal = {Journal of the ACM},
year = {2026},
doi = {10.1145/3862472},
url = {https://doi.org/10.1145/3862472}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Topic and keywords
Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- formal power series
- noncommuting variables
- rational series
- decidability
- algebraic difference equations
- differential-algebraic equations
- undecidability
Work with this paper
Most-cited papers in Computer Science
- ImageNet classification with deep convolutional neural networksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton · Communications of the ACM · 2017 · 114,726 citations
- Long Short-Term MemorySepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 109,097 citations
- A Mathematical Theory of CommunicationClaude E. Shannon · Bell System Technical Journal · 1948 · 91,736 citations
- Deep learningYann LeCun, Yoshua Bengio, Geoffrey E. Hinton · Nature · 2015 · 90,226 citations
- Faster R-CNN: Towards Real-Time Object Detection with Region Proposal NetworksShaoqing Ren, Kaiming He, Ross Girshick and 1 more · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 74,143 citations
Questions about this paper
How do I cite this paper in APA style?
Clemente, L. (2026). The commutativity problem for effective varieties of formal series, and applications. Journal of the ACM. https://doi.org/10.1145/3862472
How many times has this paper been cited?
0 times, according to OpenAlex on 18 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.
Is this paper free to read?
Yes. It is open access at Journal of the ACM: sign in and open the PDF from this page.
Who wrote this paper?
Lorenzo Clemente.
What is the DOI of this paper?
10.1145/3862472, permanently at https://doi.org/10.1145/3862472. Sign in and open it from this page.
Bibliographic data from OpenAlex (CC0), last checked 18 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.