NDLI: Observing Branching Structure through Probabilistic Contexts

Please wait, while we are loading the content...

Observing Branching Structure through Probabilistic Contexts

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Segala, Roberto Vaandrager, Frits Lynch, Nancy
Copyright Year	2007
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 ${\cal A}$, called the tester, which may announce the state of ${\cal 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 ${\cal B}$ is composed with the tester, it may generate the same external behavior as the observer only when it is able to simulate ${\cal A}$ in the sense that whenever ${\cal A}$ goes to some state s, ${\cal 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.
Starting Page	977
Ending Page	1013
Page Count	37
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539704446487
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	4
Volume Number	37
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2007-09-14
Access Restriction	Subscribed
Subject Keyword	Models of computation Modes of computation probabilistic automata trace distributions compositionality concurrency theory simulation preorder Models and methods for concurrent and distributed computing
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Observing Branching Structure through Probabilistic Contexts

Observing Branching Structure through Probabilistic Contexts

Compositionality for Probabilistic Automata (2003)

Compositionality for Probabilistic Automata (1996)

Compositionality for probabilistic automata (2003)

Abelian logic gates

Comparison Between Different Topological Models of Concurrency

Probabilistic true-concurrency models: branching cells and distributed probabilities, in "information and computation (2006).

Weak $\omega$-Regular Trace Languages

Observing Branching Structure through Probabilistic Contexts

Similar Documents

Observing Branching Structure through Probabilistic Contexts

Observing Branching Structure through Probabilistic Contexts

Compositionality for Probabilistic Automata (2003)

Compositionality for Probabilistic Automata (1996)

Compositionality for probabilistic automata (2003)

Abelian logic gates

Comparison Between Different Topological Models of Concurrency

Probabilistic true-concurrency models: branching cells and distributed probabilities, in "information and computation (2006).

Weak $\omega$-Regular Trace Languages

Observing Branching Structure through Probabilistic Contexts