Document Open Access Logo

Stream Processors and Comodels

Author Richard Garner

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2021.15.pdf
  • Filesize: 0.81 MB
  • 17 pages

Document Identifiers

Author Details

Richard Garner
  • Department of Mathematics and Statistics, Macquarie University, Sydney, Australia

Funding

  • Garner, Richard: supported by ARC grants FT160100393 and DP190102432.

Cite AsGet BibTex

Richard Garner. Stream Processors and Comodels. In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CALCO.2021.15

Abstract

In 2009, Ghani, Hancock and Pattinson gave a coalgebraic characterisation of stream processors A^ℕ → B^ℕ drawing on ideas of Brouwerian constructivism. Their stream processors have an intensional character; in this paper, we give a corresponding coalgebraic characterisation of extensional stream processors, i.e., the set of continuous functions A^ℕ → B^ℕ. Our account sites both our result and that of op. cit. within the apparatus of comodels for algebraic effects originating with Power-Shkaravska.

Subject Classification

ACM Subject Classification
  • Theory of computation → Categorical semantics
  • Theory of computation → Automata over infinite objects
Keywords
  • Comodels
  • residual comodels
  • bimodels
  • streams
  • stream processors

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Danel Ahman and Andrej Bauer. Runners in action. In Programming Languages and Systems, volume 12075 of Lecture Notes in Computer Science, pages 29-55. Springer, 2020. Google Scholar
  2. Mathieu Anel and André Joyal. Sweedler theory for (co)algebras and the bar-cobar constructions. Preprint, available as https://arxiv.org/abs/1309.6952, 2013.
  3. George M. Bergman and Adam O. Hausknecht. Co-groups and co-rings in categories of associative rings, volume 45 of Mathematical Surveys and Monographs. American Mathematical Society, 1996. Google Scholar
  4. Peter Freyd. Algebra valued functors in general and tensor products in particular. Colloquium Mathematicum, 14:89-106, 1966. Google Scholar
  5. Richard Garner. The costructure-cosemantics adjunction for comodels for computational effects. Preprint, available as https://arxiv.org/abs/2011.14520, 2020.
  6. Sergey Goncharov, Stefan Milius, and Alexandra Silva. Toward a uniform theory of effectful state machines. ACM Transactions on Computational Logic, 21, 2020. Google Scholar
  7. Peter Hancock, Dirk Pattinson, and Neil Ghani. Representations of stream processors using nested fixed points. Logical Methods in Computer Science, 5:3:9, 17, 2009. Google Scholar
  8. Martin Hyland, Gordon Plotkin, and John Power. Combining effects: sum and tensor. Theoretical Computer Science, 357:70-99, 2006. Google Scholar
  9. Bart Jacobs and Sam Staton. De Finetti’s construction as a categorical limit. In Coalgebraic methods in computer science, volume 12094 of Lecture Notes in Computer Science, pages 90-111. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-57201-3_6.
  10. Shin-ya Katsumata, Exequiel Rivas, and Tarmo Uustalu. Interaction laws of monads and comonads. Preprint, available as https://arxiv.org/abs/1912.13477, 2019.
  11. Clemens Kupke and Raul Andres Leal. Characterising behavioural equivalence: three sides of one coin. In Algebra and coalgebra in computer science, volume 5728 of Lecture Notes in Computer Science, pages 97-112. Springer, 2009. Google Scholar
  12. Paul Blain Levy. Call-by-push-value, volume 2 of Semantic Structures in Computation. Kluwer, 2003. Google Scholar
  13. Fred E. J. Linton. Some aspects of equational categories. In Conference on Categorical Algebra (La Jolla, 1965), pages 84-94. Springer, 1966. Google Scholar
  14. Jean-Pierre Meyer. Induced functors on categories of algebras. Mathematische Zeitschrift, 142:1-14, 1975. Google Scholar
  15. Rasmus Ejlers Møgelberg and Sam Staton. Linear usage of state. Logical Methods in Computer Science, 10:1:17, 52, 2014. Google Scholar
  16. Eugenio Moggi. Notions of computation and monads. Information and Computation, 93:55-92, 1991. Google Scholar
  17. Dirk Pattinson and Lutz Schröder. Sound and complete equational reasoning over comodels. In The 31st Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXI), volume 319 of Electronic Notes in Theoretical Computer Science, pages 315-331. Elsevier, 2015. Google Scholar
  18. Dirk Pattinson and Lutz Schröder. Program equivalence is coinductive. In Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science (LICS 2016), page 10. ACM, 2016. Google Scholar
  19. Gordon Plotkin and John Power. Notions of computation determine monads. In Foundations of software science and computation structures (Grenoble, 2002), volume 2303 of Lecture Notes in Computer Science, pages 342-356. Springer, Berlin, 2002. Google Scholar
  20. Gordon Plotkin and John Power. Tensors of comodels and models for operational semantics. Electronic Notes in Theoretical Computer Science, 218:295-311, 2008. Google Scholar
  21. John Power and Olha Shkaravska. From comodels to coalgebras: state and arrays. In Proceedings of the Workshop on Coalgebraic Methods in Computer Science, volume 106 of Electronic Notes in Theoretical Computer Science, pages 297-314. Elsevier, 2004. Google Scholar
  22. D. O. Tall and G. C. Wraith. Representable functors and operations on rings. Proceedings of the London Mathematical Society, 20:619-643, 1970. Google Scholar
  23. Tarmo Uustalu. Stateful runners of effectful computations. In The 31st Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXI), volume 319 of Electron. Notes Theor. Comput. Sci., pages 403-421. Elsevier Sci. B. V., Amsterdam, 2015. Google Scholar
  24. Tarmo Uustalu and Niels Voorneveld. Algebraic and coalgebraic perspectives on interaction laws. In Programming Languages and Systems, volume 12470 of Lecture Notes in Computer Science, pages 186-205. Springer, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact