Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Axiomatizations for probabilistic finite-state behaviors

yuxin Deng 1 Catuscia Palamidessi 2 
2 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : 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 definitions 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Catuscia Palamidessi Connect in order to contact the contributor
Submitted on : Sunday, December 23, 2007 - 10:47:14 PM
Last modification on : Friday, January 21, 2022 - 4:13:05 AM
Long-term archiving on: : Tuesday, April 13, 2010 - 3:37:27 PM


Files produced by the author(s)




yuxin Deng, Catuscia Palamidessi. Axiomatizations for probabilistic finite-state behaviors. 8th International Conference on Foundations of Software Science and Computational Structures (FOSSACS 2005), Apr 2005, Edinburgh, United Kingdom. pp.110-124, ⟨10.1007/b106850⟩. ⟨inria-00201123⟩



Record views


Files downloads