Axiomatizations for probabilistic finite-state behaviors

作者：Deng, Yuxin; Palamidessi, Catuscia^*

来源：Theoretical Computer Science, 2007, 373(1-2): 92-114.

DOI：10.1016/j.tcs.2006.12.008

• process calculus
• probability
• nondeterminism
• axiomatizations
• behavioral equivalences

We study a process calculus which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch's probabilistic automata. We consider various strong and weak behavioral equivalences, and we provide complete axiomatizations for finite-state processes, restricted to guarded recursion in case of the weak equivalences. We conjecture that in the general case of unguarded recursion the "natural" weak equivalences are undecidable.
This is the first work, to our knowledge, that provides a complete axiornatization for weak equivalences in the presence of recursion and both nondeterministic and probabilistic choice.

• 出版日期2007-3-22
• 单位上海交通大学; INRIA