OBSERVING BRANCHING STRUCTURE THROUGH PROBABILISTIC CONTEXTS.
Saved in:
| Title: | OBSERVING BRANCHING STRUCTURE THROUGH PROBABILISTIC CONTEXTS. |
|---|---|
| Authors: | Lynch, Nancy1 lynch@theory.csail.mit.edu, Segala, Roberto2 roberto.segala@univr.it, Vaandrager, Frits3 F.Vaandrager@cs.ru.nl |
| Source: | SIAM Journal on Computing. 2007, Vol. 37 Issue 4, p977-1013. 37p. 4 Diagrams. |
| Subjects: | Probabilistic automata, Professional Activity Study, CHOICES (Information retrieval system), Behavior modification, Machine theory, Linear operators, Composition operators, Compositionality (Linguistics), Information storage & retrieval systems, Vocational guidance |
| Abstract: | Probabilistic automata (PAs) constitute a general framework for modeling and analyzing discrete event systems that exhibit both nondeterministic and probabilistic behavior, such as distributed algorithms and network protocols. The behavior of PAs is commonly defined using schedulers (also called adversaries or strategies), which resolve all nondeterministic choices based on past history. From the resulting purely probabilistic structures, trace distributions can be extracted, whose intent is to capture the observable behavior of a PA. However, when PAs are composed via an (asynchronous) parallel composition operator, a global scheduler may establish strong correlations between the behavior of system components and, for example, resolve nondeterministic choices in one PA based on the outcome of probabilistic choices in the other. It is well known that, as a result of this, the (linear-time) trace distribution precongruence is not compositional for PAs. In his 1995 Ph.D. thesis, Segala has shown that the (branching-time) probabilistic simulation preorder is compositional for PAs. In this paper, we establish that the simulation preorder is, in fact, the coarsest refinement of the trace distribution preorder that is compositional. We prove our characterization result by providing (1) a context of a given PA A, called the tester, which may announce the state of A to the outside world, and (2) a specific global scheduler, called the observer, which ensures that the state information that is announced is actually correct. Now when another PA B is composed with the tester, it may generate the same external behavior as the observer only when it is able to simulate A in the sense that whenever A goes to some state s, B can go to a corresponding state u, from which it may generate the same external behavior. Our result shows that probabilistic contexts together with global schedulers are able to exhibit the branching structure of PAs. [ABSTRACT FROM AUTHOR] |
| Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 27872689 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: OBSERVING BRANCHING STRUCTURE THROUGH PROBABILISTIC CONTEXTS. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Lynch%2C+Nancy%22">Lynch, Nancy</searchLink><relatesTo>1</relatesTo><i> lynch@theory.csail.mit.edu</i><br /><searchLink fieldCode="AR" term="%22Segala%2C+Roberto%22">Segala, Roberto</searchLink><relatesTo>2</relatesTo><i> roberto.segala@univr.it</i><br /><searchLink fieldCode="AR" term="%22Vaandrager%2C+Frits%22">Vaandrager, Frits</searchLink><relatesTo>3</relatesTo><i> F.Vaandrager@cs.ru.nl</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Computing%22">SIAM Journal on Computing</searchLink>. 2007, Vol. 37 Issue 4, p977-1013. 37p. 4 Diagrams. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Probabilistic+automata%22">Probabilistic automata</searchLink><br /><searchLink fieldCode="DE" term="%22Professional+Activity+Study%22">Professional Activity Study</searchLink><br /><searchLink fieldCode="DE" term="%22CHOICES+%28Information+retrieval+system%29%22">CHOICES (Information retrieval system)</searchLink><br /><searchLink fieldCode="DE" term="%22Behavior+modification%22">Behavior modification</searchLink><br /><searchLink fieldCode="DE" term="%22Machine+theory%22">Machine theory</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+operators%22">Linear operators</searchLink><br /><searchLink fieldCode="DE" term="%22Composition+operators%22">Composition operators</searchLink><br /><searchLink fieldCode="DE" term="%22Compositionality+%28Linguistics%29%22">Compositionality (Linguistics)</searchLink><br /><searchLink fieldCode="DE" term="%22Information+storage+%26+retrieval+systems%22">Information storage & retrieval systems</searchLink><br /><searchLink fieldCode="DE" term="%22Vocational+guidance%22">Vocational guidance</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Probabilistic automata (PAs) constitute a general framework for modeling and analyzing discrete event systems that exhibit both nondeterministic and probabilistic behavior, such as distributed algorithms and network protocols. The behavior of PAs is commonly defined using schedulers (also called adversaries or strategies), which resolve all nondeterministic choices based on past history. From the resulting purely probabilistic structures, trace distributions can be extracted, whose intent is to capture the observable behavior of a PA. However, when PAs are composed via an (asynchronous) parallel composition operator, a global scheduler may establish strong correlations between the behavior of system components and, for example, resolve nondeterministic choices in one PA based on the outcome of probabilistic choices in the other. It is well known that, as a result of this, the (linear-time) trace distribution precongruence is not compositional for PAs. In his 1995 Ph.D. thesis, Segala has shown that the (branching-time) probabilistic simulation preorder is compositional for PAs. In this paper, we establish that the simulation preorder is, in fact, the coarsest refinement of the trace distribution preorder that is compositional. We prove our characterization result by providing (1) a context of a given PA A, called the tester, which may announce the state of A to the outside world, and (2) a specific global scheduler, called the observer, which ensures that the state information that is announced is actually correct. Now when another PA B is composed with the tester, it may generate the same external behavior as the observer only when it is able to simulate A in the sense that whenever A goes to some state s, B can go to a corresponding state u, from which it may generate the same external behavior. Our result shows that probabilistic contexts together with global schedulers are able to exhibit the branching structure of PAs. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=27872689 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/S0097539704446487 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 37 StartPage: 977 Subjects: – SubjectFull: Probabilistic automata Type: general – SubjectFull: Professional Activity Study Type: general – SubjectFull: CHOICES (Information retrieval system) Type: general – SubjectFull: Behavior modification Type: general – SubjectFull: Machine theory Type: general – SubjectFull: Linear operators Type: general – SubjectFull: Composition operators Type: general – SubjectFull: Compositionality (Linguistics) Type: general – SubjectFull: Information storage & retrieval systems Type: general – SubjectFull: Vocational guidance Type: general Titles: – TitleFull: OBSERVING BRANCHING STRUCTURE THROUGH PROBABILISTIC CONTEXTS. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Lynch, Nancy – PersonEntity: Name: NameFull: Segala, Roberto – PersonEntity: Name: NameFull: Vaandrager, Frits IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: 2007 Type: published Y: 2007 Identifiers: – Type: issn-print Value: 00975397 Numbering: – Type: volume Value: 37 – Type: issue Value: 4 Titles: – TitleFull: SIAM Journal on Computing Type: main |
| ResultId | 1 |
