Skip to Main content Skip to Navigation
Journal articles

Axiomatizations for probabilistic finite-state behaviors

Yuxin Deng 1 Catuscia Palamidessi 2
2 COMETE - Concurrency, Mobility and Transactions
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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 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.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00200928
Contributor : Catuscia Palamidessi <>
Submitted on : Saturday, December 22, 2007 - 8:35:01 AM
Last modification on : Friday, January 8, 2021 - 11:22:05 AM
Long-term archiving on: : Tuesday, April 13, 2010 - 3:12:52 PM

File

tcs.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

609

Files downloads

370