Polynomial Models for Finite Dynamical Systems

Tuesday, November 4, 2003 - 3:50pm - 4:25pm
Keller 3-180
Reinhard Laubenbacher (Virginia Polytechnic Institute and State University)
Substantial progress has been made in recent years toward a mathematical foundation for agent-based models. One advantage of such a foundation would be mathematical tools to relate the structure of the model to the resulting dynamics. This talk will focus on deterministic models with a finite state space, that is, finite dynamical systems. Under the assumption that the state set for the variables is a finite field, any such system can be described via a collection of polynomial functions with coefficients in the finite field. In particular, cellular automata and Boolean networks satisfy this assumption. Polynomial dynamical systems over finite fields are amenable to analysis with tools from computational algebra and algebraic geometry. They have been studied for some time in the context of control theory. A variety of (implemented) algorithms allows the algorithmic solution of problems such as reverse-engineering of systems with specified dynamics, as well as the computation of fixed points and limit cycles. Furthermore, computational algebra provides a rigorous framework in which to study the relationship between the structure of the rules/polynomials and the structure of the state space of the system. Several preliminary results will be discussed.