Search

Many decision problems concerning cellular automata are known to be decidable in the case of algebraic cellular automata, that is, when the state set has an algebraic structure and the automaton acts as a morphism. The most studied cases include finite fields, finite commutative rings and finite commutative groups. In this paper, we provide methods to generalize these results to the broader case of group cellular automata, that is, the case where the state set is a finite (possibly non-commutative) finite group. The configuration space is not even necessarily the full shift but a subshift — called a group shift — that is a subgroup of the full shift on ℤ d , for any number d of dimensions. We show, in particular, that injectivity, surjectivity, equicontinuity, sensitivity and nilpotency are decidable for group cellular automata, and non-transitivity is semi-decidable. Injectivity always implies surjectivity, and jointly periodic points are dense in the limit set. The Moore direction of the Garden-of-Eden theorem holds for all group cellular automata, while the Myhill direction fails in some cases. The proofs are based on effective projection operations on group shifts that are, in particular, applied on the set of valid space-time diagrams of group cellular automata. This allows one to effectively construct the traces and the limit sets of group cellular automata. A preliminary version of this work was presented at the conference Mathematical Foundations of Computer Science 2020. [ABSTRACT FROM AUTHOR]

Cellular automaton (CA) models have been used to study pedestrian evacuation for many years. The time step and pedestrian evacuation neighbourhood rules are core elements of the CA models for the study of pedestrian dynamics, which have different consequences under different conditions and, therefore, need to be taken seriously. In this paper, we combine pedestrian aggressiveness with the individual's environment and consider the pros and cons of each of their choices to optimise aggressiveness, and we discuss the impact of time step and neighbourhood rules on pedestrian dynamics under competitive conditions. Multi-velocity two-dimensional floor field cellular automaton (FFCA) is used to consider the impact of aggressiveness on speed and spatial competitiveness. After we optimise aggressiveness, the total evacuation time differs greatly from before in the multi-step method model (MSMM) when pedestrian evacuation follows Moore's neighbourhood rule. When pedestrian evacuation follows von Neumann's neighbourhood rule, in the velocity ratio method model (VRMM) and the MSMM, the total evacuation time changes with aggressiveness in the same trend, first showing the phenomenon of 'faster is faster' and then 'faster is slower', but the greater aggressiveness is, the greater the difference in evacuation time is between the two models. When pedestrian evacuation follows Moore's neighbourhood rule, the total evacuation time has opposite trends to aggressiveness under the VRMM and the MSMM. In addition, in the VRMM, the total evacuation time of pedestrians following von Neumann's neighbourhood rule is always much greater, almost twice as long, than when following Moore's neighbourhood rule. In the MSMM, the difference in the total pedestrian evacuation time following different neighbourhood rules is much more complicated. • Pedestrian aggressiveness is optimised, considering the pedestrian's environment and the pros and cons of the choices, and compared to when it is unoptimised. • A multi-step method model for pedestrian evacuation is proposed and compared with the speed ratio method model, and how to deal with the conflicts caused by the multi-step method is explained. • Highlight the impact of the coupling effects of different neighbourhood rules and time step methods on pedestrian evacuation when considering aggressiveness. [ABSTRACT FROM AUTHOR]