{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:11:10Z","timestamp":1767337870955,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,1,17]],"date-time":"2024-01-17T00:00:00Z","timestamp":1705449600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2024,1,31]]},"abstract":"<jats:p>\n            We study connections among polynomials, differential equations, and streams over a field \ud835\udd42, in terms of algebra and coalgebra. We first introduce the class of\n            <jats:italic>(F,G)<\/jats:italic>\n            -\n            <jats:italic>products<\/jats:italic>\n            on streams, those where the stream derivative of a product can be expressed as a polynomial function of the streams and their derivatives. Our first result is that, for every\n            <jats:italic>(F,G)<\/jats:italic>\n            -product, there is a canonical way to construct a transition function on polynomials such that the resulting unique final coalgebra morphism from polynomials into streams is the (unique) commutative \ud835\udd42-algebra homomorphism\u2014and vice versa. This implies that one can algebraically reason on streams via their polynomial representation. We apply this result to obtain an algebraic-geometric decision algorithm for polynomial stream equivalence, for an underlying generic\n            <jats:italic>(F,G)<\/jats:italic>\n            -product. Finally, we extend this algorithm to solve a more general problem: finding all valid polynomial equalities that fit in a user specified polynomial template.\n          <\/jats:p>","DOI":"10.1145\/3632747","type":"journal-article","created":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T11:36:07Z","timestamp":1699961767000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Products, Polynomials and Differential Equations in the Stream Calculus"],"prefix":"10.1145","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1972-7491","authenticated-orcid":false,"given":"Michele","family":"Boreale","sequence":"first","affiliation":[{"name":"Universit\u00e0 degli Studi di Firenze, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-7967-4119","authenticated-orcid":false,"given":"Luisa","family":"Collodi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Firenze, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8859-9844","authenticated-orcid":false,"given":"Daniele","family":"Gorla","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,1,17]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_3_2_2","DOI":"10.1007\/978-3-319-06880-0_6"},{"doi-asserted-by":"publisher","key":"e_1_3_3_3_2","DOI":"10.1017\/S0960129517000159"},{"issue":"1","key":"e_1_3_3_4_2","first-page":"38","article-title":"Coalgebras for bisimulation of weighted automata over semirings.","volume":"19","author":"Bhaduri Purandar","year":"2023","unstructured":"Purandar Bhaduri. 2023. Coalgebras for bisimulation of weighted automata over semirings. Log. Methods Comput. Sci. 19, 1 (2023), 38\u201366.","journal-title":"Log. Methods Comput. Sci."},{"doi-asserted-by":"publisher","key":"e_1_3_3_5_2","DOI":"10.1016\/j.ic.2011.12.002"},{"key":"e_1_3_3_6_2","first-page":"20:1\u201320:9","article-title":"Coinduction up-to in a fibrational setting.","author":"Bonchi Filippo","year":"2014","unstructured":"Filippo Bonchi, Daniela Petrisan, Damien Pous, and Jurriaan Rot. 2014. Coinduction up-to in a fibrational setting. In Proceedings of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) and the 29th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). 20:1\u201320:9.","journal-title":"Proceedings of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) and the 29th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)"},{"issue":"3","key":"e_1_3_3_7_2","article-title":"Presenting distributive laws.","volume":"11","author":"Bonsangue Marcello","year":"2017","unstructured":"Marcello Bonsangue, Helle Hvid Hansen, Alexander Kurze, and Jurriaan Rot. 2017. Presenting distributive laws. Log. Methods Comput. Sci., 11, 3 (2015), 1\u201323. https:\/\/lmcs.episciences.org\/1578\/pdf","journal-title":"Log. Methods Comput. Sci."},{"key":"e_1_3_3_8_2","first-page":"Springer, 163\u20131","article-title":"Weighted bisimulation in linear algebraic form.","author":"Boreale Michele","year":"2009","unstructured":"Michele Boreale. 2009. Weighted bisimulation in linear algebraic form. In Proceedings of CONCUR 2009. M. Bravetti and G. Zavattaro (Eds.), Lecture Notes in Computer Science, Vol. 5710, Springer, 163\u2013177.","journal-title":"Proceedings of CONCUR 2009"},{"issue":"1","key":"e_1_3_3_9_2","article-title":"Algebra, coalgebra, and minimization in polynomial differential equations.","volume":"15","author":"Boreale Michele","year":"2019","unstructured":"Michele Boreale. 2019. Algebra, coalgebra, and minimization in polynomial differential equations. Log. Methods Comput. Sci. 15, 1 (2019), 14:1\u201314:27. https:\/\/lmcs.episciences.org\/5192\/pdf","journal-title":"Log. Methods Comput. Sci."},{"key":"e_1_3_3_10_2","first-page":"24:1\u201324:13","article-title":"On the coalgebra of partial differential equations.","author":"Boreale Michele","year":"2019","unstructured":"Michele Boreale. 2019. On the coalgebra of partial differential equations. In Proceedings of the MFCS, Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen (Eds.). LIPIcs,Vol. 138, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 24:1\u201324:13.","journal-title":"Proceedings of the MFCS"},{"key":"e_1_3_3_11_2","first-page":"Vol. 12289, Spr","article-title":"Automatic pre- and postconditions for partial differential equations.","author":"Boreale Michele","year":"2020","unstructured":"Michele Boreale. 2020. Automatic pre- and postconditions for partial differential equations. Proceedings of the 17th International Conference on Quantitative Evaluation of Systems. M. Gribaudo, D. N. Jansen, A. Remke (Eds.), Lecture Notes in Computer Science, Vol. 12289, Springer, 193\u2013210.","journal-title":"Proceedings of the 17th International Conference on Quantitative Evaluation of Systems"},{"doi-asserted-by":"publisher","key":"e_1_3_3_12_2","DOI":"10.1016\/j.scico.2020.102441"},{"key":"e_1_3_3_13_2","first-page":"19:1\u201319:17","article-title":"Algebra and coalgebra of stream products. In","author":"Boreale Michele","year":"2021","unstructured":"Michele Boreale and Daniele Gorla. 2021. Algebra and coalgebra of stream products. In Proceedings of the 32nd International Conference on Concurrency Theory. 19:1\u201319:17.","journal-title":"Proceedings of the 32nd International Conference on Concurrency Theory"},{"doi-asserted-by":"publisher","key":"e_1_3_3_14_2","DOI":"10.1007\/978-0-387-35651-8"},{"key":"e_1_3_3_15_2","article-title":"How to write a coequation ((co) algebraic pearls). In","author":"Dahlqvist Fredrik","year":"2021","unstructured":"Fredrik Dahlqvist and Todd Schmid. 2021. How to write a coequation ((co) algebraic pearls). In Proceedings of the 9th Conference on Algebra and Coalgebra in Computer Science Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik.","journal-title":"Proceedings of the 9th Conference on Algebra and Coalgebra in Computer Science"},{"doi-asserted-by":"publisher","key":"e_1_3_3_16_2","DOI":"10.1007\/BF00121127"},{"unstructured":"Philippe Flajolet and Robert Sedgewick. 2001. Analytic Combinatorics: Functional Equations Rational and Algebraic Functions. Research Report RR-4103 INRIA.","key":"e_1_3_3_17_2"},{"issue":"1","key":"e_1_3_3_18_2","article-title":"Stream differential equations: Specification formats and solution methods.","volume":"13","author":"Hansen Helle Hvid","year":"2017","unstructured":"Helle Hvid Hansen, Clemens Kupke, and Jan Rutten. 2017. Stream differential equations: Specification formats and solution methods. Log. Methods Comput. Sci. 13, 1 (2017), 1\u201351. https:\/\/lmcs.episciences.org\/3118\/pdf","journal-title":"Log. Methods Comput. Sci."},{"key":"e_1_3_3_19_2","volume-title":"Nonlinear Systems (3rd ed.).","author":"Khalil Hassan","year":"2002","unstructured":"Hassan Khalil. 2002. Nonlinear Systems (3rd ed.).Prentice Hall."},{"doi-asserted-by":"publisher","key":"e_1_3_3_20_2","DOI":"10.1016\/j.tcs.2011.03.023"},{"doi-asserted-by":"publisher","key":"e_1_3_3_21_2","DOI":"10.1007\/s00500-016-2363-z"},{"doi-asserted-by":"publisher","key":"e_1_3_3_22_2","DOI":"10.1007\/978-3-642-69959-7"},{"unstructured":"Christian Mallinger. 1996. Algorithmic manipulations and transformations of univariate holonomic functions and sequences. Diplomarbeit Johannes Kepler Universitat Linz.","key":"e_1_3_3_23_2"},{"issue":"3","key":"e_1_3_3_24_2","first-page":"563-609","article-title":"Trajectories of polynomial vector fields and ascending chains of polynomial ideals.","volume":"49","author":"Novikov Dmitri","year":"2011","unstructured":"Dmitri Novikov and Sergei Yakovenko.2011. Trajectories of polynomial vector fields and ascending chains of polynomial ideals. Ann. Inst. Fourier 49, 3 (1999), 563-609.","journal-title":"Ann. Inst. Fourier"},{"key":"e_1_3_3_25_2","volume-title":"The On-line Encyclopedia of Integer Sequences.","author":"OEIS","year":"1996","unstructured":"OEIS 1996. The On-line Encyclopedia of Integer Sequences.Retrieved from https:\/\/oeis.org"},{"key":"e_1_3_3_26_2","first-page":"408","article-title":"Calculus in coinductive form.","author":"Pavlovic Dusko","year":"1998","unstructured":"Dusko Pavlovic and Martin Escard\u00f3. 1998. Calculus in coinductive form. In Proceedings of the LICS. 408\u2013417.","journal-title":"Proceedings of the LICS"},{"doi-asserted-by":"publisher","key":"e_1_3_3_27_2","DOI":"10.1016\/S0304-3975(02)00895-2"},{"doi-asserted-by":"publisher","key":"e_1_3_3_28_2","DOI":"10.1017\/S0960129504004517"},{"key":"e_1_3_3_29_2","volume-title":"The Method of Coalgebra: Exercises in Coinduction.","author":"Rutten Jan","year":"2019","unstructured":"Jan Rutten. 2019. The Method of Coalgebra: Exercises in Coinduction.CWI, Amsterdam."},{"doi-asserted-by":"publisher","key":"e_1_3_3_30_2","DOI":"10.1145\/964001.964028"},{"key":"e_1_3_3_31_2","volume-title":"Enumerative Combinatorics","author":"Stanley Richard P.","year":"2012","unstructured":"Richard P. Stanley. 2012. Enumerative Combinatorics(2nd ed.). CUP."},{"key":"e_1_3_3_32_2","volume-title":"Coalgebraic Characterizations of Automata-Theoretic Classes.","author":"Winter Joost","year":"2014","unstructured":"Joost Winter. 2014. Coalgebraic Characterizations of Automata-Theoretic Classes.Ph. D. Dissertation. Radboud Universiteit Nijmegen."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632747","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632747","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:51:04Z","timestamp":1750287064000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632747"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,17]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,31]]}},"alternative-id":["10.1145\/3632747"],"URL":"https:\/\/doi.org\/10.1145\/3632747","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2024,1,17]]},"assertion":[{"value":"2022-10-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-10","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}