Department
Computer Science
Major
Applied Mathematics
Research Advisor
Thakur, Mayur
Advisor's Department
Computer Science
Abstract
We introduce models for stochastic sequential dynamical systems (Ssos), an extension of sequential dynamical systems. We introduce the Random Value and Random Update models of Ssos, as well as defining the p-PROBABLEPREDECESSOR- EXISTENCE problem (p-PPRE problem), which is a generalization of the PREDECESSOR-EXISTENCE problem to the stochastic realm. The p-PPRE problem asks, given a configuration C and Ssos S, whether or not there exists a configuration C' such that Pr[S(C1=C] ≥ p. We show that, given specific restrictions on the underlying graph of Sand its local transition functions, we can apply methods used in the non-stochastic case to solve this problem in polynomial time with respect to the number of nodes in S.
Biography
Matthew Austin is a graduating senior in Applied Mathematics who is also pursuing minors in Computer Science and Physics. 21
Research Category
Natural Sciences
Presentation Type
Oral Presentation
Document Type
Presentation
Location
Havener Center, Meramec Room
Presentation Date
11 April 2007, 9:00 am - 9:30 am
Stochastic Sequential Dynamical Systems
Havener Center, Meramec Room
We introduce models for stochastic sequential dynamical systems (Ssos), an extension of sequential dynamical systems. We introduce the Random Value and Random Update models of Ssos, as well as defining the p-PROBABLEPREDECESSOR- EXISTENCE problem (p-PPRE problem), which is a generalization of the PREDECESSOR-EXISTENCE problem to the stochastic realm. The p-PPRE problem asks, given a configuration C and Ssos S, whether or not there exists a configuration C' such that Pr[S(C1=C] ≥ p. We show that, given specific restrictions on the underlying graph of Sand its local transition functions, we can apply methods used in the non-stochastic case to solve this problem in polynomial time with respect to the number of nodes in S.
