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.
Type de document :
Communication dans un congrès
Vladimiro Sassone. 8th International Conference on Foundations of Software Science and Computational Structures (FOSSACS 2005), Apr 2005, Edinburgh, United Kingdom. Springer, 3441, pp.110-124, 2005, Lecture Notes in Computer Science. 〈10.1007/b106850〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00201123
Contributeur : Catuscia Palamidessi <>
Soumis le : dimanche 23 décembre 2007 - 22:47:14
Dernière modification le : jeudi 15 novembre 2018 - 20:26:59
Document(s) archivé(s) le : mardi 13 avril 2010 - 15:37:27

Fichier

fossacs05.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Yuxin Deng, Catuscia Palamidessi. Axiomatizations for probabilistic finite-state behaviors. Vladimiro Sassone. 8th International Conference on Foundations of Software Science and Computational Structures (FOSSACS 2005), Apr 2005, Edinburgh, United Kingdom. Springer, 3441, pp.110-124, 2005, Lecture Notes in Computer Science. 〈10.1007/b106850〉. 〈inria-00201123〉

Partager

Métriques

Consultations de la notice

557

Téléchargements de fichiers

192