Properties of Quantum Languages

The class of quantum languages Q() over an alphabet is the class of languages accepted by quantum automata. We study properties of Q() and compare Q() with the class of regular languages R(). It is shown that Q() is closed under union, intersection, and reversal but is not closed under complementation, concatenation, or Kleene star. It is also shown that Q() and R() are incomparable. Finally, we prove that L Q() if and only if L admits a transition amplitude function satisfying a certain property and a similar characterization is given for R().     

Discrete threshold growth dynamics are omnivorous for box neighborhoods

In the discrete threshold model for crystal growth in the plane we begin with some set of seed crystals and observe crystal growth over time by generating a sequence of subsets of by a deterministic rule. This rule is as follows: a site crystallizes when a threshold number of crystallized points appear in the site's prescribed neighborhood. The growth dynamics generated by this model are said to be omnivorous if finite and imply . In this paper we prove that the dynamics are omnivorous when the neighborhood is a box (i.e. when, for some fixed , the neighborhood of is . This result has important implications in the study of the first passage time when is chosen randomly with a sparse Bernoulli density and in the study of the limiting shape to which converges.

     

Parrondo Games as Lattice Gas Automata

Parrondo games are coin flipping games with the surprising property that alternating plays of two losing games can produce a winning game. We show that this phenomenon can be modelled by probabilistic lattice gas automata. Furthermore, motivated by the recent introduction of quantum coin flipping games, we show that quantum lattice gas automata provide an interesting definition for quantum Parrondo games.     

Diffusion in Lorentz lattice gas cellular automata: The honeycomb and quasi-lattices compared with the square and triangular lattices

We study numerically the nature of the diffusion process on a honeycomb and a quasi-lattice, where a point particle, moving along the bonds of the lattice, scatters from randomly placed scatterers on the lattice sites according to strictly deterministic rules. For the honeycomb lattice fully occupied by fixed rotators two (symmetric) isolated critical points appear to be present, with the same hyperscaling relation as for the square and the triangular lattices. No such points appear to exist for the quasi-lattice. A comprehensive comparison is made with the behavior on the previously studied square and triangular lattices. A great variety of diffusive behavior is found, ranging from propagation, superdiffusion, normal, quasi-normal, and anomalous, to absence of diffusion. The influence of the scattering rules as well as of the lattice structure on the diffusive behavior of a point particle moving on the all lattices studied so far is summarized.     

A Survey on Topological Properties of Tiles Related to Number Systems

In the present paper we give an overview of topological properties of self-affine tiles. After reviewing some basic results on self-affine tiles and their boundary we give criteria for their local connectivity and connectivity. Furthermore, we study the connectivity of the interior of a family of tiles associated to quadratic number systems and give results on their fundamental group. If a self-affine tile tessellates the space the structure of the set of its ‘neighbors’ is discussed.     

On The Sum of Digits Function for Number Systems with Negative Bases

Let q 2 be an integer. Then –q gives rise to a number system in , i.e., each number n has a unique representation of the form n = c ₀ + c ₁ (–q) + ... + c _h (–q) ^h , with c _i {0,..., q – 1}(0 i h). The aim of this paper is to investigate the sum of digits function _–q (n) of these number systems. In particular, we derive an asymptotic expansion for

One-Dimensional Lattice Dynamics of the Diffusion-Limited Reaction A+A→A+S: Transient Behavior

We use a Boolean cellular automaton model to describe the diffusion-limited dynamics of the irreversible reaction A+AA+S on a 1D lattice. We derive a set of equations for the dynamics of the empty interval probabilities from which explicit expressions for the particle concentration and the two-point correlation can be obtained. It is shown that the long-time dynamics is in agreement with the off-lattice solution. The early-time behavior, however, predicts a slower decay of the concentration.     

Cellular automata for the spreading of technologies in socio-economic systems

We introduce an agent-based model for the spreading of technological developments in socio-economic systems where the technology is mainly used for the collaboration/interaction of agents. Agents use products of different technologies to collaborate with each other which induce costs proportional to the difference of technological levels. Additional costs arise when technologies of different providers are used. Agents can adopt technologies and providers of their interacting partners in order to reduce their costs leading to microscopic rearrangements of the system. Analytical calculations and computer simulations revealed that starting from a random configuration of different technological levels a complex time evolution emerges where the spreading of advanced technologies and the overall technological progress of the system are determined by the amount of advantages more advanced technologies provide, and by the structure of the social environment of agents. We show that agents tend to form clusters of identical technological level with a power law size distribution. When technological progress arises, the spreading of technologies in the system can be described by extreme order statistics.     

Genetic algorithms and cellular automata in aquifer management

A groundwater management problem is presented involving pumping cost minimization with both well discharges and well locations as decision variables. A grid of candidate well locations is set up and optimal arrangements of wells are sought within this discrete space. A genetic algorithm approach is presented with the following particular features: (a) A suitable scaling is applied to the objective function in order to alleviate its regionally flat behavior. (b) No penalty functions are involved in constraint handling. Instead, the feasible region is transformed into a rectangular domain. The transformation introduced is proved to be bijective. (c) A binary representation of well configurations is presented and compared to a combinatorial one. The binary representation necessitates the introduction of specially designed genetic operators. Besides purely genetic algorithms, the concept of cellular automaton is introduced as the basis of an alternative formulation of the optimization problem. The lattice of the cellular automaton provides the discrete set of candidate well positions. The well configuration is represented by a group of agents occupying an equal number of lattice sites. The agents change positions as dictated by the structure of the automaton and, also, by an associated genetic algorithm, which directs the evolution of the whole scheme toward an optimal configuration. An improved performance of this approach is noted and discussed in comparison to the purely genetic algorithm schemes of the present work. A simulated annealing approach is also applied to the same problem for comparison purposes. Finally, a new and more efficient hybrid annealing–genetic approach is introduced and discussed.