I detta papper studerar vi familjen av två-state Totalistic Freezing Cellular Automata (TFCA) definieras över triangulära och fyrkantiga rutnät med von Neumann stadsdelar. Vi säger att en Cellular Automaton är Frysande och Totalistisk om de aktiva cellerna förblir oförändrade, och det nya värdet av en inaktiv cell beror endast på summan av dess aktiva grannar. Vi klassificerar alla Cellular Automata i klassen TFCA, grupperar dem i fem olika klasser: Trivial reglerna, Turing universella regler, Algebraiska regler, Topological regler och Fractal Growing regler. Samtidigt studerar vi i denna familj stabilitetsproblemet, som består i att avgöra om en inaktiv cell blir aktiv, med tanke på en inledande konfiguration. Vi utnyttjar egenskaperna hos automaten i varje grupp för att visa att: • För algebraiska och topologiska regler är stabilitetsproblem i NC. • För Turing Universella regler är stabilitetsproblemet P-Complete.
Mer nyligen, i REF föreslås en studie av komplexiteten i 32 olika tvådimensionella och två-state totalistic frys CA (2FTCA) med von Neumann grannskapet.
On the Complexity of the Stability Problem of Binary Freezing Totalistic Cellular Automata
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Physics']}