Goncharov S (2023)
Publication Type: Conference contribution
Publication year: 2023
Publisher: Springer Science and Business Media Deutschland GmbH
Book Volume: 13710 LNCS
Pages Range: 100-120
Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Event location: Aveiro, PRT
ISBN: 9783031433443
DOI: 10.1007/978-3-031-43345-0_5
Notions of iteration range from the arguably most general Elgot iteration to a very specific Kleene iteration. The fundamental nature of Elgot iteration has been extensively explored by Bloom and Esik in the form of iteration theories, while Kleene iteration became extremely popular as an integral part of (untyped) formalisms, such as automata theory, regular expressions and Kleene algebra. Here, we establish a formal connection between Elgot iteration and Kleene iteration in the form of Elgot monads and Kleene monads, respectively. We also introduce a novel class of while-monads, which like Kleene monads admit a relatively simple description in algebraic terms. Like Elgot monads, while-monads cover a large variety of models that meaningfully support while-loops, but may fail the Kleene algebra laws, or even fail to support a Kleen iteration operator altogether.
APA:
Goncharov, S. (2023). Shades of Iteration: From Elgot to Kleene. In Alexandre Madeira, Manuel A. Martins (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 100-120). Aveiro, PRT: Springer Science and Business Media Deutschland GmbH.
MLA:
Goncharov, Sergey. "Shades of Iteration: From Elgot to Kleene." Proceedings of the 26th IFIP WG 1.3 International Workshop on Algebraic Development Techniques, WADT 2022, Aveiro, PRT Ed. Alexandre Madeira, Manuel A. Martins, Springer Science and Business Media Deutschland GmbH, 2023. 100-120.
BibTeX: Download