Sound and Complete Axiomatization of Trace Semantics for Probabilistic Systems
- Citation:
- Silva A, Sokolova A. 2011. Sound and Complete Axiomatization of Trace Semantics for Probabilistic Systems. Proceedings of the Twenty-seventh Conference on the Mathematical Foundations of Programming Semantics (MFPS '11). 276:291––311.
Tertiary Title:
Electronic Notes in Theoretical Computer ScienceDate Presented:
MayAbstract:
Coalgebras provide a uniform framework to study dynamical systems, including several types of automata. In this paper, we make use of the coalgebraic view on systems to investigate, in a uniform way, under which conditions calculi that are sound and complete with respect to behavioral equivalence can be extended to a coarser coalgebraic language equivalence, which arises from a generalised powerset construction. We illustrate the framework with two examples: non-deterministic automata, for which we recover Rabinovich’s sound and complete calculus for language equivalence, and weighted automata, for which we present the first sound and complete calculus for weighted language equivalence.
Citation Key:
SS11DOI:
10.1016/j.entcs.2011.09.027
Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.