Sound and Complete Axiomatization of Trace Semantics for Probabilistic Systems
Alexandra Soares da Silva, Ana Sokolova · Electronic Notes in Theoretical Computer Science · 2011
We present a sound and complete axiomatization of finite complete trace semantics for generative probabilistic transition systems. Our approach is coalgebraic, which opens the door to axiomatize other types of systems. In order to prove soundness and completeness, we employ determinization and show that coalgebraic traces can be recovered via determinization, a result interesting in itself. The approach is also applicable to labelled transition systems, for which we can recover the known axiomatization of trace semantics (work of Rabinovich).