7,038 research outputs found
Libretto di sala - 1992 - Claudio Santambrogio e Marino Formenti
No full textClaudio Santambrogio, flautoMarino Formenti, pianofort
The first humans travelling on ice: an energy-saving strategy?
No full textEconomy of locomotion is a constant challenge for animals, particularly when related to migrations and travelling. The present study focuses on human locomotion and particularly on the development of ice skating. The aim of our research was to understand whether an environmental feature such as a strong presence of lakes (frozen in winter) could force humans to develop ice skates in order to limit the energy cost of travelling. We hypothesized that the energy-saving principle was a determinant factor in the development of human locomotion on ice. Five healthy adult participants took part in the experiments, during which we recorded the speed (1.2 ± 0.3 m s−1) and metabolic energy cost (4.6 ± 0.9 J kg−1 m−1) associated with travelling on bone skates. Simulations were also performed to demonstrate whether the benefit given by the use of skates was different in the areas where ice skating appears to have evolved originally. The gain reachable by using bone skates could lead to an extremely high energy saving (equal to 10% of the energy needed to survive during the cold season) and differs significantly between the regions considered in the present study. An analysis of the geometrical shape of lakes associated with fractal analysis of their distribution suggests that, in order to better adapt to the severe conditions imposed by the long lasting winters, Finnish populations could benefit more than others from developing this ingenious locomotion tool. © 2008 The Linnean Society of London, Biological Journal of the Linnean Society, 2008, 93, 1–7
Hard to Detect Factors of Univariate Integer Polynomials
No full textWe investigate the computational complexity of deciding whether a given univariate integer polynomial p(x) has a factor q(x) satisfying specific additional constraints. When the only constraint imposed on q(x) is to have a degree smaller than the degree of p(x) and greater than zero, the problem is equivalent to testing the irreducibility of p(x) and then it is solvable in polynomial time. We prove that deciding whether a given monic univariate integer polynomial has factors satisfying additional properties is NP-complete in the strong sense. In particular, given any constant value k∈Z, we prove that it is NP-complete in the strong sense to detect the existence of a factor that returns a prescribed value when evaluated at x=k (Theorem 1) or to detect the existence of a pair of factors—whose product is equal to the original polynomial—that return the same value when evaluated at x=k (Theorem 2). The list of all the properties we have investigated in this paper is reported at the end of Section Introduction
Reaction systems and extremal combinatorics properties
No full textExtremal combinatorics is the study of the size that a collection of objects must have in order to certainly satisfy a given property. Reaction systems are a recent formalism for computation inspired by chemical reactions. This work is a first contribution to the study of the behavior of large reaction systems by means of extremal combinatorics. We define several different properties that capture some basic and dynamical behaviors of a reaction system and we prove that they must necessarily be satisfied if the system is large enough. Explicit bounds and formulae are also provided
From Linear to Additive Cellular Automata
No full textThis paper proves the decidability of several important properties of additive cellular automata over finite abelian groups. First of all, we prove that equicontinuity and sensitivity to initial conditions are decidable for a nontrivial subclass of additive cellular automata, namely, the linear cellular automata over n, where is the ring Z/mZ. The proof of this last result has required to prove a general result on the powers of matrices over a commutative ring which is of interest in its own. Then, we extend the decidability result concerning sensitivity and equicontinuity to the whole class of additive cellular automata over a finite abelian group and for such a class we also prove the decidability of topological transitivity and all the properties (as, for instance, ergodicity) that are equivalent to it. Finally, a decidable characterization of injectivity and surjectivity for additive cellular automata over a finite abelian group is provided in terms of injectivity and surjectivity of an associated linear cellular automata over n
An Easy to Check Characterization of Positive Expansivity for Additive Cellular Automata over a Finite Abelian Group
No full textAdditive cellular automata over a finite abelian group are a wide class of cellular automata (CA) that are able to exhibit most of the complex behaviors of general CA and they are often exploited for designing applications in different practical contexts. We provide an easy to check algebraic characterization of positive expansivity for Additive Cellular Automata over a finite abelian group. We stress that positive expansivity is an important property that defines a condition of strong chaos for CA and, for this reason, an easy to check characterization of positive expansivity turns out to be crucial for designing proper applications based on Additive CA and where a condition of strong chaos is required. First of all, in the paper an easy to check algebraic characterization of positive expansivity is provided for the non trivial subclass of Linear Cellular Automata over the alphabet (Z/mZ)n . Then, we show how it can be exploited to decide positive expansivity for the whole class of Additive Cellular Automata over a finite abelian group
An Efficient Algorithm Deciding Chaos for Linear Cellular Automata over (Z/mZ)n with Applications to Data Encryption
No full textWe provide an efficient algorithm deciding chaos for linear cellular automata (LCA) over (Z/mZ)^n, a large and important class of cellular automata (CA) which may exhibit many of the complex features typical of general CA and are used in many applications. The efficiency of our algorithm is mainly due to fact that it avoids the computation of the prime factor decomposition of m which is a well-known difficult task. Instead of factoring m we make use of a new and efficient generalized technique for computing the greatest common divisor (gcd) of polynomials with coefficients not belonging to a field, which in itself is an interesting result. We wish also to emphasize that the gcd computations required by our algorithm always involve polynomials of degree at most n. We also illustrate the impact of our algorithm in real-world applications regarding the growing domain of cryptosystems, the latter being often based on LCA over (Z/mZ)^n with n>1. As a matter of facts, since cryptosystems have to satisfy the so-called confusion and diffusion properties (which are ensured if the involved LCA is chaotic) our algorithm turns out to be an important tool for building chaotic LCA over (Z/mZ)^n and, hence, for improving the existing methods based on them
On the Dynamical Behavior of Cellular Automata on Finite Groups
No full textDuring the last few decades, significant efforts have been devoted to analyze the dynamical behavior of cellular automata (CAs) on cyclic groups, their Cartesian power (referred to as linear cellular automata), and on general abelian groups (referred to as additive cellular automata). Many fundamental properties describing the dynamical behavior of a system such as injectivity, surjectivity, sentitivity to the initial conditions, topological transitivity, ergodicity, positive expansivity, denseness of periodic orbits, and chaos have been fully characterized for these classes of cellular automata, i.e., the relation between the cellular automaton (CA) local rule and the CA global behavior was made explicit, being this task a challenging and important problem in CA general theory. A natural step forward leads to investigate the dynamical behavior of group cellular automata, i.e., cellular automata defined on (not necessarily abelian) finite groups. Despite the work recently carried out by some authors, none of the previously mentioned properties has yet been fully characterized in the case of general finite groups. In this paper, we study the dynamical behavior of cellular automata on a number of classes of finite groups such as simple, symmetric, alternating, dihedral, quaternion and decomposable groups and we provide exact characterizations for some of the above mentioned properties. To do this, in each of those classes, we focus our attention to the non-abelian scenarios. Some results are quite surprising because they show that the non-abelianness of the group imposes strong limitations on defining the local rule of the cellular automaton, making the class of group cellular automata very constrained. Finally, we also introduce a graph allowing one to build and study the local rules of any group cellular automaton
Computing issues of asynchronous CA
No full textThis work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are “universal”, i.e., allowing a (specific family of) ACA to simulate any Turing machine on any input. We also consider the computational cost of such simulations. Finally, we deal with ACA equipped with peculiar updating sequences, namely those generated by random walks
- …
