Fuzzy cellular automata are dynamical systems that are continuous counterparts of the usual cellular automata (CA). Compared with the binary case, defining a fuzzy CA with three or more states is challenging because defining mixed states is difficult. Recently, this difficulty was resolved by representing multiple states as independent vectors in higher dimensions, and the concept of vector-valued fuzzy CA (VFCA) was introduced. In this study, we theoretically analyze and discuss the asymptotic behavior of three-neighbor VFCA. First, we define the weighted-averaging rules of VFCA and show how many rules exist up to the equivalence relations. According to these rules, each state vector in the next step is determined by the weighted average of the vectors in its neighboring cells. Next, we prove that three-state VFCA with weighted-averaging rules converge to a periodic configuration characterized by the symmetric group of order 3. In particular, the non-commutativity of the group action provides an interesting behavior that is not observed in fuzzy CA arising from binary states. Finally, we extend the results to VFCA with more than three states.

Abstract. Max-plus algebra is a semiring with addition [Formula: see text] and multiplication [Formula: see text]. It is applied in cases such as combinatorial optimization and discrete event systems. We consider the power of max-plus square matrices, which is equivalent to obtaining the all-pair maximum weight paths with a fixed length in the corresponding weighted digraph. Each [Formula: see text]-by-[Formula: see text] matrix admits the CSR expansion that decomposes the matrix into a sum of at most [Formula: see text] periodic terms after [Formula: see text] times of powers. In this study, we propose an [Formula: see text] time algorithm for the CSR expansion, where [Formula: see text] is the number of nonzero entries in the matrix, which improves the [Formula: see text] algorithm known for this problem. Our algorithm is based on finding the roots of the characteristic polynomial of the max-plus matrix. These roots play a similar role to the eigenvalues of the matrix and become the growth rates of the terms in the CSR expansion.