Steps and traces. (23rd August 2021)

• Record Type: Journal Article
• Authors: Rot, Jurriaan; Jacobs, Bart; Levy, Paul Blain
• Is Part Of: Journal of logic and computation. Volume 31:Number 6(2021)
• Page Start: 1482
• Page End: 1525
• Publication Date: 2021-08-23
• Subjects: Coalgebra -- trace semantics -- corecursive algebras; Logic programming -- Periodicals; Logic, Symbolic and mathematical -- Periodicals; Computational complexity -- Periodicals; 005.115
• DOI: 10.1093/logcom/exab050
• Languages: English
• ISSNs: 0955-792X

Abstract

Abstract: In the theory of coalgebras, trace semantics can be defined in various distinct ways, including through algebraic logics, the Kleisli category of a monad or its Eilenberg–Moore category. This paper elaborates two new unifying ideas: (i) coalgebraic, draftrules trace semantics is naturally presented in terms of corecursive algebras, and (ii) all three approaches arise as instances of the same abstract setting. Our perspective puts the different approaches under a common roof and allows to derive conditions under which some of them coincide.