Traffic dispersion induced by noise in off-lattice model

We study the dispersion of vehicles induced by speed fluctuation on a single-lane highway under open boundary. We extend the cellular automaton model on one-dimensional lattice to the real-variable model on off-lattice (continuous-in space model) in order to take into account the fluctuation of vehicular speed. Vehicles extend over the highway when moving forward. The characteristics of traffic dispersion are derived. It is shown that vehicular traffic exhibits scaling property. When a vehicle accelerates for following the vehicle ahead, vehicles move forming a cluster without dispersion. The relationship between the width of vehicular cluster and acceleration rate is clarified.     

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.     

The Automaton Realization of Iterated Wreath Products of Cyclic Groups

We study profinite groups which are infinitely iterated wreath products W _∞ = …?C _{n 2} ?C _{n 1} of finite cyclic groups via combinatorial language of transducers. Namely, we provide a naturally defined automaton realization of the group W _∞ by an automaton over a changing alphabet. Our construction gives a characterization of these profinite groups as automaton groups, i.e. as groups generated by a single automaton.     

Cells as strain-cued automata

We argue in favor of representing living cells as automata and review demonstrations that autonomous cells can form patterns by responding to local variations in the strain fields that arise from their individual or collective motions. An autonomous cell's response to strain stimuli is assumed to be effected by internally-generated, internally-powered forces, which generally move the cell in directions other than those implied by external energy gradients. Evidence of cells acting as strain-cued automata have been inferred from patterns observed in nature and from experiments conducted in vitro. Simulations that mimic particular cases of pattern forming share the idealization that cells are assumed to pass information among themselves solely via mechanical boundary conditions, i.e., the tractions and displacements present at their membranes. This assumption opens three mechanisms for pattern formation in large cell populations: wavelike behavior, kinematic feedback in cell motility that can lead to sliding and rotational patterns, and directed migration during invasions. Wavelike behavior among ameloblast cells during amelogenesis (the formation of dental enamel) has been inferred from enamel microstructure, while strain waves in populations of epithelial cells have been observed in vitro. One hypothesized kinematic feedback mechanism, “enhanced shear motility”, accounts successfully for the spontaneous formation of layered patterns during amelogenesis in the mouse incisor. Directed migration is exemplified by a theory of invader cells that sense and respond to the strains they themselves create in the host population as they invade it: analysis shows that the strain fields contain positional information that could aid the formation of cell network structures, stabilizing the slender geometry of branches and helping govern the frequency of branch bifurcation and branch coalescence (the formation of closed networks). In simulations of pattern formation in homogeneous populations and network formation by invaders, morphological outcomes are governed by the ratio of the rates of two competing time dependent processes, one a migration velocity and the other a relaxation velocity related to the propagation of strain information. Relaxation velocities are approximately constant for different species and organs, whereas cell migration rates vary by three orders of magnitude. We conjecture that developmental processes use rapid cell migration to achieve certain outcomes, and slow migration to achieve others. We infer from analysis of host relaxation during network formation that a transition exists in the mechanical response of a host cell from animate to inanimate behavior when its strain changes at a rate that exceeds 10⁻⁴–10⁻³ s⁻¹. The transition has previously been observed in experiments conducted in vitro.     

Supervisory control of hybrid systems based on model abstraction and guided search

This paper addresses the task of computing supervisory controllers by which hybrid systems with nonlinear continuous dynamics are driven into goal sets while safety specifications are met. For this class of systems, the (conservatively approximative) determination of reachable states is an important but also a computationally expensive step of the controller synthesis. This contribution proposes a technique aiming at reducing the reach set computation by using abstract models and guided search. For a discrete abstraction of the hybrid model, candidate paths are determined as possible controlled evolutions which fulfill the given specifications. A validation scheme comprising three different techniques is applied to determine whether the candidate path represents a feasible control strategy for the hybrid system. If the specification is violated, the abstract model is refined according to the validation result. The iterative application of the determination of candidate paths, the path validation and the model refinement steers the search for a control strategy such that often only a relatively small part of the reachable state space has to be explored. The synthesis procedure is illustrated for two examples.     

关于 Fuzzyω正则语言的一个注记

通过引入ω-Nerode等价关系,fuzzy前逆缀ω-语言,闭左逆语言等概念来研究语言的化数性质,得到了(1)fuzzyω正则语言可由一些具有有限指标集的等价类来表示;(2)fuzzy前逆缀ω-语言是fuzzyω正则语言iff由L定义的ω-Nerode等价关系的指标集是有限的.     

关于Fuzzy正则语言的一些性质

在定义Fuzzy正则语言,Fuzzy有理语言等的基础上,研究Fuzzy正则语言相关的一些性质,得到Fuzzy正则语言与Fuzzy有理语言间的对应关系,对Fuzzy有限状态自动机的简化具有应用价值。     

The Lamplighter Group ℤ3≀ℤ Generated by a Bireversible Automaton

We construct a bireversible self-dual automaton with three states over an alphabet with three letters which generates the lamplighter group ?₃??. In particular, this fact shows that not all groups defined by birevirsible automata are finitely presented.     

Ordering sequences by permutation transducers

To extend a natural concept of equivalence of sequences to two-sided infinite sequences, the notion of permutation transducer is introduced. Requiring the underlying automaton to be deterministic in two directions, it provides the means to rewrite bi-infinite sequences. The first steps in studying the ensuing hierarchy of equivalence classes of bi-infinite sequences are taken, by describing the classes of ultimately periodic two-sided infinite sequences. It is important to make a distinction between unpointed and pointed sequences, that is, whether or not sequences are considered equivalent up to shifts. While one-sided ultimately periodic sequences form a single equivalence class under ordinary transductions, which is shown to split into two under permutation transductions, in the two-sided case there are three unpointed and seven pointed equivalence classes under permutation transduction.