Axiomatizations for probabilistic finite-state behaviors

Yuxin Deng; Catuscia Palamidessi

doi:10.1007/978-3-540-31982-5_7

Axiomatizations for probabilistic finite-state behaviors

Yuxin Deng
, Catuscia Palamidessi

INRIA

Résultats de recherche: Contribution à un journal › Article de conférence › Revue par des pairs

14 Citations (Scopus)

Résumé

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.

langue originale	Anglais
Pages (de - à)	110-124
Nombre de pages	15
journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3441
Les DOIs	https://doi.org/10.1007/978-3-540-31982-5_7
état	Publié - 1 janv. 2005
Evénement	8th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2005, held as part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2005 - Edinburgh, Royaume-Uni Durée: 4 avr. 2005 → 8 avr. 2005

Accès au document

10.1007/978-3-540-31982-5_7

Contient cette citation

@article{36a910606aa241f7ab9ed69662c952d8,

title = "Axiomatizations for probabilistic finite-state behaviors",

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.",

author = "Yuxin Deng and Catuscia Palamidessi",

year = "2005",

month = jan,

day = "1",

doi = "10.1007/978-3-540-31982-5\_7",

language = "English",

volume = "3441",

pages = "110--124",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

note = "8th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2005, held as part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2005 ; Conference date: 04-04-2005 Through 08-04-2005",

}

Axiomatizations for probabilistic finite-state behaviors. / Deng, Yuxin; Palamidessi, Catuscia.
Dans: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol 3441, 01.01.2005, p. 110-124.

Résultats de recherche: Contribution à un journal › Article de conférence › Revue par des pairs

TY - JOUR

T1 - Axiomatizations for probabilistic finite-state behaviors

AU - Deng, Yuxin

AU - Palamidessi, Catuscia

PY - 2005/1/1

Y1 - 2005/1/1

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-31982-5_7

DO - 10.1007/978-3-540-31982-5_7

M3 - Conference article

AN - SCOPUS:24644492522

SN - 0302-9743

VL - 3441

SP - 110

EP - 124

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 8th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2005, held as part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2005

Y2 - 4 April 2005 through 8 April 2005

ER -

Axiomatizations for probabilistic finite-state behaviors

Résumé

Accès au document

Empreinte digitale

Contient cette citation