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