Axiomatizations for probabilistic finite-state behaviors - Archive ouverte HAL Access content directly
Journal Articles Theoretical Computer Science Year : 2007

Axiomatizations for probabilistic finite-state behaviors

(1) , (2)


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 axiomatization for weak equivalences in the presence of recursion and both nondeterministic and probabilistic choice.
Fichier principal
Vignette du fichier
tcs.pdf (679.64 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00200928 , version 1 (22-12-2007)



Yuxin Deng, Catuscia Palamidessi. Axiomatizations for probabilistic finite-state behaviors. Theoretical Computer Science, 2007, 373 (1-2), pp.92-114. ⟨10.1016/j.tcs.2006.12.008⟩. ⟨inria-00200928⟩
262 View
101 Download



Gmail Facebook Twitter LinkedIn More