License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2021.19
URN: urn:nbn:de:0030-drops-143969
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14396/
Go to the corresponding LIPIcs Volume Portal

Boreale, Michele ; Gorla, Daniele

Algebra and Coalgebra of Stream Products

pdf-format:
LIPIcs-CONCUR-2021-19.pdf (0.7 MB)

Abstract

We study connections among polynomials, differential equations and streams over a field ?, in terms of algebra and coalgebra. We first introduce the class of (F,G)-products on streams, those where the stream derivative of a product can be expressed as a polynomial of the streams themselves and their derivatives. Our first result is that, for every (F,G)-product, there is a canonical way to construct a transition function on polynomials such that the induced unique final coalgebra morphism from polynomials into streams is the (unique) ?-algebra homomorphism - and vice-versa. This implies one can reason algebraically 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 (F,G)-product. As an example of reasoning on streams, we focus on specific products (convolution, shuffle, Hadamard) and show how to obtain closed forms of algebraic generating functions of combinatorial sequences, as well as solutions of nonlinear ordinary differential equations.

BibTeX - Entry

@InProceedings{boreale_et_al:LIPIcs.CONCUR.2021.19,
  author =	{Boreale, Michele and Gorla, Daniele},
  title =	{{Algebra and Coalgebra of Stream Products}},
  booktitle =	{32nd International Conference on Concurrency Theory (CONCUR 2021)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-203-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{203},
  editor =	{Haddad, Serge and Varacca, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14396},
  URN =		{urn:nbn:de:0030-drops-143969},
  doi =		{10.4230/LIPIcs.CONCUR.2021.19},
  annote =	{Keywords: Streams, coalgebras, polynomials, differential equations}
}

Keywords: Streams, coalgebras, polynomials, differential equations
Collection: 32nd International Conference on Concurrency Theory (CONCUR 2021)
Issue Date: 2021
Date of publication: 13.08.2021
Supplementary Material: Software (Source Code): https://local.disia.unifi.it/boreale/papers/streams.py

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI