On some algorithms for reverse engineering certain finite dynamical systems

Abstract

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.