Options
Counting fixed points and pure 2-cycles of tree cellular automata
Publikationstyp
Conference Paper
Date Issued
2024
Sprache
English
Author(s)
First published in
Number in series
14579
Volume
14579 LNCS
Start Page
241
End Page
256
Citation
Theoretical Informatics, LATIN 2024
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Springer Nature Switzerland
ISBN
978-3-031-55601-2
978-3-031-55600-5
978-3-031-55602-9
Cellular 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.
Subjects
Counting problems
Fixed points
Tree cellular automata
DDC Class
620: Engineering