On some algorithms for reverse engineering certain finite dynamical systems

View/ Open
Author
Orozco, Edusmildo
Advisor
Bollman, DorothyType
DissertationCollege
College of EngineeringProgram
Computing and Information Sciences and EngineeringDepartment
Department of Electrical and Computer EngineeringDegree Level
Ph.D.Date
2005Metadata
Show full item recordAbstract
There are two general problems related to finite dynamical systems (FDS): the analysis and the synthesis (also known as the reverse engineering) problems. In the former, we are interested in uncovering the sequential structure of a given FDS. In the latter, given a prescribed structure, we have to find an appropriate FDS that accomplishes the intended behavior. In this work we reverse engineer FDSs related to two recent applications. On is the problem of finding an optimal linear (i.e., a matrix) FDS over the integers mod a prime p to efficiently compute FFTs with linear symmetries. For this, we propose O(p2logp) and o(p3logp) time algorithms for the two and three dimensional cases as opposed to O(p6) and O(p12) time of exhaustive searches, respectively. Also, we characterize those important cases for which he symmetric FFT with prime edge-length can be computed through a single cyclic convolution. For the second problem, the reverse engineering problem in bioinformatics, we study and compare two finite field models for genetic networks and provide algorithms for converting one model into the other via a DFT. Also, we develop efficient methods for performing arithmetic over finite fields. We propose a new efficient parallel algorithm based in the Chines remaindering theorem to interpolate over finite fields.