Search

We characterize interval Mobius number systems with sofic expansion subshifts and show that they can be obtained as factors of interval Mobius number systems with expansion subshifts of finite types. The endpoints of interval cylinders of such systems can be computed by a simple formula which generalizes the computation of Farey fractions in the Stern–Brocot graph. We treat in detail the bimodular number system which has many nice properties and could be used for exact real computer arithmetic.

Given a finite alphabet A, a system of real orientation-preserving Mobius transformations , a subshift and an interval cover of , we consider the expansion subshift of all expansions of real numbers with respect to . If the expansion quotient is greater than 1 then there exists a continuous and surjective symbolic mapping and we say that is a Mobius number system. We apply our theory to the system of binary continued fractions which is a combination of the binary signed system with the continued fractions, and to the binary square system whose transformations have stable fixed points −1, 0, 1 and ∞.

The distribution of species abundances within an ecological community provides a window into ecological processes and has important applications in conservation biology as an indicator of disturbance. Previous work indicates that species abundance distributions might be independent of the scales at which they are measured which has implications for data interpretation. Here we formulate an analytically tractable model for the species abundance distribution at different scales and discuss the biological relevance of its assumptions. Our model shows that as scale increases, the shape of the species abundance distribution converges to a particular shape given uniquely by the Jaccard index of spatial species turnover and by a parameter for the spatial correlation of abundances. Our model indicates that the shape of the species abundance distribution is taxon specific but does not depend on sample area, provided this area is large. We conclude that the species abundance distribution may indeed serve as an indicator of disturbances affecting species spatial turnover and that the assumption of conservation of energy in ecosystems, which is part of the Maximum Entropy approach, should be re-evaluated.

A real M?bius iterative system is an action of a free semigroup of finite words acting via M?bius transformations on the extended real line. Its convergence space consists of all infinite words, such that the images of the Cauchy measure by the prefixes of the word converge to a point measure. A M?bius number system consists of a M?bius iterative system and a subshift included in the convergence space, such that any point measure can be obtained as the limit of some word of the subshift. We give some sufficient conditions on sofic subshifts to form M?bius number systems. We apply our theory to several number systems based on continued fractions.

We investigate iterative systems consisting of Mobius transformations on the extended real line. We characterize systems with unique attractor and give some sufficient conditions for minimality.

We describe symbolic representations of the extended real line based on the dynamical systems consisting of Mobius transformations. The representations can be extended to the group of real Mobius transformations.

Arithmetical algorithms considered in Chap. 5 are based on the arithmetical operations with matrices of the number systems. If the entries of these matrices are not integers or rationals, we need arithmetical algorithms which work with them. Such algorithms exist for algebraic numbers. Algebraic numbers can be represented by vectors or matrices of rational numbers. Arithmetical operations with them are based on matrix calculus.

When we compute arithmetical algorithms in a sofic number system, we perform arithmetical operations with the entries of its transformations, intervals and vectors. These operations are algorithmic provided the entries are rational numbers. Since we work with projective matrices and vectors, we can assume that their entries are integers whose greatest common divisor is 1. Then each projective tensor, matrix or vector with rational entries has exactly two representations with coprime integers.

A number system specifies the representation of real numbers by symbolic sequences, so its key element is the value mapping \(\Phi : \Sigma \rightarrow \overline{\mathbb {R}}\). Mobius number systems are based on representations of real numbers by sequences of Mobius transformations, so the alphabet of the subshift \(\Sigma \) consists of the symbols of the transformations. We have several means how to define suitable subshifts \(\Sigma \) and suitable value mappings \(\Phi \).

As we have seen in Chap. 1, the digits of a number system correspond to transformations which are in all cases Mobius transformations of the form \(M(x) = \frac{ax+b}{cx+d}\).

We introduce the concept of limit set associated to a cellular automaton (CA) and a shift invariant probability measure. This is a subshift whose forbidden blocks are exactly those, whose probabilities tend to zero as time tends to infinity. We compare this probabilistic concept of limit set with the concepts of attractors, both in topological and measure-theoretic sense. We also compare this notion with that of topological limit set in different dynamical situations.

We measure the complexity of dynamical systems on zero-dimensional compact metric spaces by the complexity of formal languages, which these systems generate on clopen partitions of the state space. We show that in the classes of recursive, context-sensitive, context-free, regular, etc., languages there exist universal dynamical systems which yield, by factor maps, all dynamical systems of the class. Universal systems are not unique, but in every class there exists a smallest universal system.

Given a rotation of the circle, we study the complexity of formal languages that are generated by the itineraries of interval covers. These languages are regular iff the rotation is rational. In the case of irrational rotations, our study reduces to that of the language complexity of the corresponding Sturmian sequences. We show that for a large class of irrationals, including e, all quadratic numbers and more generally all Hurwitz numbers, the corresponding languages can be recognized by a nondeterministic Turing machine in linear time (in other words, belongs to NLIN).

We show that the only analytic functions computable by finite state transducers in sofic Mobius number systems are Mobius transformations.

We consider three related classifications of cellular automata: the first is based on the complexity of languages generated by clopen partitions of the state space, i.e. on the complexity of the factor subshifts; the second is based on the concept of equicontinuity and it is a modification of the classification introduced by Gilman [9]. The third one is based on the concept of attractors and it refines the classification introduced by Hurley [16]. We show relations between these classifications and give examples of cellular automata in the intersection classes. In particular, we show that every positively expansive cellular automaton is conjugate to a one-sided subshift of finite type and that every topologically transitive cellular automaton is sensitive to initial conditions. We also construct a cellular automaton with minimal quasi-attractor, whose basin has measure zero, answering a question raised in Hurley [16].

International audience; Modular Möbius number systems consist of Möbius transformations with integer coefficients and unit determinant. We show that in any modular Möbius number system, the computation of a Möbius transformation with integer coefficients can be performed by a finite state transducer and has linear time complexity. As a byproduct we show that every modular Möbius number system has the expansion subshift of finite type.

Dynamical systems at the edge of chaos, which have been considered as models of self-organization phenomena, are marked by their ability to perform nontrivial computations. To distinguish them from systems with limited computing power, we formulate two simplicity criteria for general dynamical systems, and apply them to unimodal systems on real interval. We say that a dynamical system is regular, if it yields a regular language when observed through arbitrary almost disjoint cover. Finite automata are regarded as dynamical systems on zero-dimensional spaces and their factors yield another class of simple dynamical systems. These two criteria coincide on subshifts, since a subshift is regular iff it is a factor of a finite automaton (sofic systems). A unimodal system on real interval is regular if it has only a finite number of periodic points, and nonrecursive otherwise. On the other hand each $S$-unimodal system with finite, periodic or preperiodic kneading sequence is a factor of a finite automaton. Thus preperiodic $S$-unimodal systems are factors of finite automata, which are not regular., Comment: Presented at the workshop "Continuous Algorithms and Complexity", Barcelona 4-6. October 1993. Latex

We study the parameter space of an iterative system consisting of two hyperbolic disc Mobius transformations. We identify several classes of parameters which yield discrete groups whose fundamental polygons have sides at the Euclidean boundary. It follows that these system are not minimal.

International audience; We describe a heuristic algorithm which searches for spreading clopen sets of a cellular automaton. Then the algorithms searches for the corresponding subshift attractors (which are omega-limits of spreading sets found) as forward images of joins of signal subshifts.

We consider a class of thermodynamic systems in which the dynamics of the spontaneous approach to equilibrium is governed by the gradient of negentropy, where the gradient is taken with respect to a Riemannian metric. In open systems (dissipative structures) this gradient field is superposed with a vector field of interactions with environment. We consider three characteristics of the “economy” of dissipative structures: negentropy inflow (income), negentropy consumption (i.e. entropy production), and negentropy surplus (reserves). We derive explicit formulas for these characteristics and for the relations between them.

This is an overview of some classical and recent results in topological dynamics of cellular automata on the space of twosided symbolic sequences. The concepts studied include surjectivity, transitivity, equicontinuity, closingness, openness, expansivity, attractors and the shadowing property.

International audience; We construct an algorithm which finds the maximal attractors (limit sets) of certain cellular automata whose maximal attractor is a sofic subshift. The algorithm first finds signal subshifts of a given automaton, constructs their join, and finally forward images of this join. When this procedure stops, the algorithm tests whether a special condition of decreasing preimages is satisfied. If so, the maximal attractor has been attained.

A description is given of an approach to the objective qualification and quantification of information obtained by secondary electron imaging of the three-dimensional shape and surface ultrastructure of cells grown attached to the flat substratum in vitro. Objective cell assessment in the SEM (OCAS) is based on the evaluation of cell phenotype in standard defined culture conditions according to a fixed protocol. The human capacity to analyse complex images is used for the elementary collection of data and this is analysed by computerised mathematical processing. The OCAS method described was tested on a training set of populations of mostly rat mesenchymal normal and neoplastic cells. The results show a significant correlation between OCAS data structures describing a cell population and the following biological properties: malignancy, tumorigenicity, virogenicity and growth properties in vitro. These findings correspond to those of others and to an intuitive evaluation of the secondary electron SEM images of cells. In a detailed analysis the OCAS differences were screened for the indicative power to show the particular biological properties of the investigated cells. This was achieved by varying the representation of the OCAS variables in all three groups used: microecology, cell shape, and surface ultrastructure. It was found that the variable which describes the cell surface features points out tumorigenicity and malignancy while the width/height ratio alone indicates tumorigenicity. When these two criteria are combined, then all important biological properties coming into consideration (malignancy, tumorigenicity, virogenicity and growth properties in vitro) are shown. If only microecological criteria are used, then anchorage independence alone is revealed. This led to the conclusion that, for the prediction of malignancy, just the surface ultrastructure, especially the presence of various microvilli, and the three-dimensional shape of the mesenchymal cell in vitro are decisive. Microecological criteria can be omitted unless the adaptation to the growth under in vitro conditions is investigated. Moreover, from our results it follows that the expression of the influences of neoplastic transformation (tumorigenicity) and the adaption to growth in vitro (anchorage independent growth) on the cell morpho-type are to some extent at variance, which deserves further study.

An enzyme cluster is a system of enzymes attached to a membrane, whose spatial organization makes it possible for the product of one enzymatic reaction tobe directly available as a substrate of another reaction within the cluster. We show how to model enzyme clusters by Markov chains, and how to compute their overall reaction rate. As a by-product we prove a formula for the number of completed cycles per unit time in a Markov chain.

We investigate finite state, continuous time Markov chains, whose transition rates have different orders of magnitude. Such a chain may be approximated by a simple one, which is obtained by grouping together states whose mutual communication is of the highest order. Using this reduced chain, the computation of both transition probability matrix and stationary distribution of the original chain is simplified significantly. The method is applicable in enzyme kenetics, and presumably in mathematical ecology or population genetics.

An evolutionary model based on the Taylor-Jonker game dynamics is presented. A set of strategies is compatible if there exists a dynamical equilibrium between its members and there is an evolutionary transition to another compatible set if new mutant strategies bring about a passage to another equilibrium. We apply these concepts to supergame strategies, which play repeatedly a given matrix game and at each time step choose their pure strategy according to the preceding moves of the opponent. We investigate the patterns of evolution in zero-sum games, games of partnership, the prisoner's dilemma and the hawkdove game.

Grammars in general categories are investigated. A topological condition on applicability of a production to an object is given.

We generalize the class of sofic subshifts, which correspond to regular languages, to subshifts accepted by either nondeterministic or deterministic Turing machines in real time. We show that every substitutive system can be accepted by a deterministic Turing machine in real time.

We consider a model of Darwinian evolution in games with perfect information like chess or checkers. The evolution is viewed as a sequence of strategies, each of which wins over its immediate predecessor. We argue that the intelligence level of strategies need not necessarily increase during this type of evolution.

Grammars in general categories are investigated. A topological condition on applicability of a production to an object is given.

We propose a mathematical model for the malformation incidence in a population. The model is based on the assumption that malformations occur in a narrow range of embryotoxic doses for a given toxin and that this range varies in the population. Using this assumption, we exhibit malformation incidence curves which are in qualitative agreement with experimental data.

A mathematical model of replicator evolution is considered. Replicators are words of a formal language specifying a strategy for a parlour game. They replicate with mutations and are selected according to their pay-off against other replicators.

Many different definitions of computational universality for various types of dynamical systems have flourished since Turing's work. We propose a general definition of universality that applies to arbitrary discrete time symbolic dynamical systems. Universality of a system is defined as undecidability of a model-checking problem. For Turing machines, counter machines and tag systems, our definition coincides with the classical one. It yields, however, a new definition for cellular automata and subshifts. Our definition is robust with respect to initial condition, which is a desirable feature for physical realizability. We derive necessary conditions for undecidability and universality. For instance, a universal system must have a sensitive point and a proper subsystem. We conjecture that universal systems have infinite number of subsystems. We also discuss the thesis according to which computation should occur at the `edge of chaos' and we exhibit a universal chaotic system., 23 pages; a shorter version is submitted to conference MCU 2004 v2: minor orthographic changes v3: section 5.2 (collatz functions) mathematically improved v4: orthographic corrections, one reference added v5:27 pages. Important modifications. The formalism is strengthened: temporal logic replaced by finite automata. New results. Submitted

We show relations between several concepts of stability based on topological and measure-theoretical concepts in the Cantor and Besicovitch topological spaces. These concepts elucidate the behavior of cellular automata in which successively larger and larger regions are homogenized.

We modify the idea of a previous article [8] and introduce polynomial and exponential dynamically defined recurrence dimensions, topological invariants which express how the Poincare recurrence time of a set grows when the diameter of the set shrinks. We introduce also the concept of polynomial entropy which applies in the case that topological entropy is zero and complexity function is polynomial. We compare recurrence dimensions with topological and polynomial entropies, evaluate recurrence dimensions of Sturmian subshifts and show some examples with Toeplitz subshifts.