Luciano Margara

We investigate the relationships between dynamical complexity and the set of periodic configurations of surjective Cellular Automata. We focus on the set of strictly temporally periodic configurations, i.e., the set of those configurations which are

The present knowledge of protein structures at atomic level derives from some 60,000 molecules. Yet the exponential ever growing set of hypothetical protein sequences comprises some 10 million chains and this makes the problem of protein structure prediction one of the challenging goals of bioinformatics. In this context, the protein representation with contact maps is an intermediate step of fold recognition and constitutes the input of contact map predictors. However contact map representations require fast and reliable methods to reconstruct the specific folding of the protein backbone.

Cellular Automata (CA) are discrete dynamical systems and an abstract model of parallel computation. The limit set of a cellular automaton is its maximal topological attractor. A well know result, due to Kari, says that all nontrivial properties of limit sets are undecidable. In this paper we consider properties of limit set dynamics, i.e. properties of the dynamics of Cellular Automata restricted to their limit sets. There can be no equivalent of Kari's Theorem for limit set dynamics. Anyway we show that there is a large class of undecidable properties of limit set dynamics, namely all properties of limit set dynamics which imply stability or the existence of a unique subshift attractor. As a consequence we have that it is undecidable whether the cellular automaton map restricted to the limit set is the identity, closing, injective, expansive, positively expansive, transitive.

The problem of protein structure prediction is one of the long-standing goals of Computational Biology. Although we are still not able to provide first principle solutions, several shortcuts have been discovered to compute the protein three-dimensional structure when similar protein sequences are available (by means of comparative modeling and remote homology detection). Nonetheless, these approaches can assign structures only to a fraction of proteins in genomes and ab-initio methods are still needed. One relevant step of ab-initio prediction methods is the reconstruction of the protein structures starting from inter-protein residue contacts. In this paper we review the methods developed so far to accomplish the reconstruction task in order to highlight their differences and similarities. The different approaches are fully described and their reported performances, together with their computational complexity, are also discussed.

In this paper we consider the problem of inverting an n × n n\times n circulant matrix with entries over Z m \mathbf {Z}_m . We show that the algorithm for inverting circulants, based on the reduction to diagonal form by means of FFT, has some drawbacks when working over Z m \mathbf {Z}_m . We present three different algorithms which do not use this approach. Our algorithms require different degrees of knowledge of m m and n n , and their costs range, roughly, from n log ⁡ n log ⁡ log ⁡ n n\log n\log \log n to n log 2 ⁡ n log ⁡ log ⁡ n log ⁡ m n \log ^2n\log \log n \log m operations over Z m \mathbf {Z}_m . Moreover, for each algorithm we give the cost in terms of bit operations. We also present an algorithm for the inversion of finitely generated bi-infinite Toeplitz matrices. The problems considered in this paper have applications to the theory of linear cellular automata.