Hasuo, Ichiro and Jacobs, Bart and Sokolova, Ana - Generic Trace Semantics via Coinduction

lmcs:864 - Logical Methods in Computer Science, November 19, 2007, Volume 3, Issue 4
Generic Trace Semantics via Coinduction

Authors: Hasuo, Ichiro and Jacobs, Bart and Sokolova, Ana

Trace semantics has been defined for various kinds of state-based systems, notably with different forms of branching such as non-determinism vs. probability. In this paper we claim to identify one underlying mathematical structure behind these "trace semantics," namely coinduction in a Kleisli category. This claim is based on our technical result that, under a suitably order-enriched setting, a final coalgebra in a Kleisli category is given by an initial algebra in the category Sets. Formerly the theory of coalgebras has been employed mostly in Sets where coinduction yields a finer process semantics of bisimilarity. Therefore this paper extends the application field of coalgebras, providing a new instance of the principle "process semantics via coinduction."

Source : oai:arXiv.org:0710.2505
DOI : 10.2168/LMCS-3(4:11)2007
Volume: Volume 3, Issue 4
Published on: November 19, 2007
Submitted on: July 21, 2007
Keywords: Computer Science - Logic in Computer Science,F.3.1,F.3.2,G.3


Consultation statistics

This page has been seen 116 times.
This article's PDF has been downloaded 80 times.