Turau, VolkerVolkerTurau2024-04-082024-04-082024LATIN 2024: Theoretical Informatics : 16th Latin American Symposium, Puerto Varas, Chile, March 18–22, 2024, Proceedings. - Cham, 2024. - (Lecture Notes in Computer Science ; vol. 14579). - Seite 241–256978-3-031-55601-2978-3-031-55600-5978-3-031-55602-9https://hdl.handle.net/11420/46851Cellular automata are synchronous discrete dynamical systems used to describe complex dynamic behaviors. The dynamic is based on local interactions between the components, these are defined by a finite graph with an initial node coloring with two colors. In each step, all nodes change their current color synchronously to the least/most frequent color in their neighborhood and in case of a tie, keep their current color. After a finite number of rounds these systems either reach a fixed point or enter a 2-cycle. The problem of counting the number of fixed points for cellular automata is #P-complete. In this paper we consider cellular automata defined by a tree. We propose an algorithm with run-time O(nΔ) to count the number of fixed points, here Δ is the maximal degree of the tree. We also prove upper and lower bounds for the number of fixed points. Furthermore, we obtain corresponding results for pure cycles, i.e., instances where each node changes its color in every round. We provide examples demonstrating that the bounds are sharp.enCounting problemsFixed pointsTree cellular automataEngineering and Applied OperationsConference Paper10.1007/978-3-031-55601-2_16Conference Paper