On free semigroups of automaton transformations

It is established that the subset of freek-generated subsemigroups of the semigroup of all automaton transformations over a finite alphabet is a second category set (in the sense of the Baire category approach) in the set of allk-generated subsemigroups. A continuum series of pairs of automaton transformations each of which generates a free semigroup of rank two is indicated. A criterion is established for this semigroup to be a finite-automaton group. Translated fromMatematicheskie Zametki, Vol. 63, No. 2, pp. 248–259, February, 1998. The author wishes to express his deep gratitude to Professor V. I. Sushchans'kii for permanent help and attention to the research. This research was partially supported by the ISSEP under grant No. GSU 051341.     

On a free group of transformations defined by an automaton

We prove that three automorphisms of the rooted binary tree defined by a certain 3-state automaton generate a free non-Abelian group of rank 3. Both authors are supported by the NSF grants DMS-0308985 and DMS-0456185. Yaroslav Vorobets is supported by a Clay Research Scholarship.     

On the complexity of the word problem for automaton semigroups and automaton groups

In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and automaton groups, we introduce automaton-inverse semigroups, which are generated by partial, yet invertible automata. We show that there is an automaton-inverse semigroup and, thus, an automaton semigroup with a PSpace-complete word problem. We also show that there is an automaton group for which the word problem with a single rational constraint is PSpace-complete. Additionally, we provide simpler constructions for the uniform word problems of these classes. For the uniform word problem for automaton groups (without rational constraints), we show NL-hardness. Finally, we investigate a question asked by Cain about a better upper bound for the length of a word on which two distinct elements of an automaton semigroup must act differently.A detailed listing of the contributions of this paper can be found at the end of this paper.     

A non-ergodic probabilistic cellular automaton with a unique invariant measure

We exhibit a Probabilistic Cellular Automaton (PCA) on {0,1}^Z with a neighborhood of size 2 which is non-ergodic although it has a unique invariant measure. This answers by the negative an old open question on whether uniqueness of the invariant measure implies ergodicity for a PCA.     

The semigroup of a strongly connected automaton

We show that each member of a class of strongly connected automata (containing all the finite ones) whose input semigroup is the semigroup of the automaton is isomorphic to an automaton (A,S,) where S is a semigroup of row-monomial matrices over a group G, A is a set of equivalence classes of monomial vectors over G and is the usual product of a matrix acting on a vector.     

Quantum automaton in a 1-D box

A simple cellular automaton is conjectured based on the Dirac wave equation and a diffusion confinement which attempts to emulate quantum behaviour of a particle in a 1-D box. Some features of quantum behavior such as the collapse of the wave function upon measurement, the wave-like nature of particles, and the role of virtual and non-local interactions become evident after completing a series of computations and analyzing the results. A pronounced correspondence between an automaton and a quantum particle in a 1-D box is explicated and shows promise for explaining some of the cloudy conceptual difficulties enmeshed in present quantum space-time pictures of reality.     

On a Newton-Moser type method

We prove that a variant of Moser's iterative method for solving nonlinear equations is quadratically convergent and give error bounds. We estimate the amount of arithmetic for the method and compare it to Newton's method. Finally we use the method to solve a problem with small divisors.     

On a Littlewood-Paley type inequality

The following is proved: If is a function harmonic in the unit ball and if then the inequality

holds, where is the nontangential maximal function of This improves a recent result of Stoll. This inequality holds for polyharmonic and hyperbolically harmonic functions as well.

     

A cellular automaton technique for modelling of a binary dendritic growth with convection

A two-dimensional model for the simulation of a binary dendritic growth with convection has been developed in order to investigate the effects of convection on dendritic morphologies. The model is based on a cellular automaton (CA) technique for the calculation of the evolution of solid/liquid (s/l) interface. The dynamics of the interface controlled by temperature, solute diffusion and Gibbs–Thomson effects, is coupled with the continuum model for energy, solute and momentum transfer with liquid convection. The solid fraction is calculated by a governing equation, instead of some approximate methods such as lever rule method [A. Jacot, M. Rappaz, Acta Mater. 50 (2002) 1909–1926.] or interface velocity method [L. Nastac, Acta Mater. 47 (1999) 4253; L. Beltran-Sanchez, D.M. Stefanescu, Mat. and Mat. Trans. A 26 (2003) 367.]. For the dendritic growth without convection, mesh independency of simulation results is achieved. The simulated steady-state tip velocity are compared with the predicted values of LGK theory [Lipton, M.E. Glicksmanm, W. Kurz, Metall. Trans. 18(A) (1987) 341.] as a function of melt undercooling, which shows good agreement. The growth of dendrite arms in a forced convection has been investigated. It was found that the dendritic growth in the upstream direction was amplified, due to larger solute gradient in the liquid ahead of the s/l interface caused by melt convection. In the isothermal environment, the calculated results under very fine mesh are in good agreement with the Oseen–Ivanstov solution for the concentration-driven growth in a forced flow.     

On the zero dynamics of linear nonstationary discrete systems with a single input and a scalar output

For a linear discrete nonstationary system with one-dimensional input and output, we find conditions for the existence of a feedback providing the existence of a subspace L _t of constant nonzero dimension such that this subspace is invariant under the closed system and the output variable is zero for all motions in this subspace. Under certain assumptions, we indicate equations that describe the solutions located in L _t . A criterion is established for the subspace L _t to be stationary (i.e., independent of t).     

On Hanner type inequalities with a weight for Banach spaces

We shall present several Hanner type inequalities with a weight constant and characterize 2-uniformly smooth and 2-uniformly convex Banach spaces with these inequalities. p-Uniformly smooth and q-uniformly convex Banach spaces will be also characterized with another Hanner type inequalities with a weight in the other side term. The best value of the weight in these inequalities will be determined for Lp spaces. Also we shall present a duality theorem between these inequalities in a generalized form.     

Fuzzy正则表达式与Fuzzy有限态自动机的关系

首先给出了Fuzzy正则表达式的定义,接着通过研究Fuzzy正则表达式与Fuzzy有限态自动机的关系,得到了两个重要性质,即：每一个Fuzzy正则表达式,都有一个非确定性的Fuzzy有限态自动机接受其代表的语言;每一个被确定性的Fuzzy有限态自动机接受的语言,都能被一个Fuzzy正则表达式表示．     

The mathematical solution of a cellular automaton model which simulates traffic flow with a slow-to-start effect

In this paper we investigate a cellular automaton model associated with traffic flow and of which the mathematical solution is unknown before. We classify all kinds of stationary states and show that every state finally evolves to a stationary state. The obtained flow-density relation shows multiple branches corresponding to the stationary states in congested phases, which are essentially due to the slow-to-start effect introduced into this model. The stability of these states is formulated by a series of lemmas, and an algorithm is given to calculate the stationary state that the current state finally evolves to. This algorithm has a computational requirement in proportion to the number of cars.