Electronic Notes in Theoretical Computer Science · 2009 · 24 citations · 21 references
ComputingComputer ScienceMathematicsDynamical SystemsLogicProbability TheoryAutomata TheoryBoolean AlgebraCellular AutomataComputational ModelsFinite AutomataFuzzy LogicAsymptotic AnalysisCellular Automaton ModelingContinuous Cellular AutomataDensityDisjunctive Normal FormFixed Point PropertyFuzzy AutomataMean Field Analysis
Fuzzy cellular automata (FCA) are continuous cellular automata where the local rule is defined as the “fuzzification” of the local rule of a corresponding Boolean cellular automaton in disjunctive normal form. In this paper we are interested in the relationship between Boolean and fuzzy models and we analytically show, for the first time, the existence of a strong connection between them by focusing on two properties: density conservation and additivity. We begin by giving a probabilistic interpretation of our fuzzification which leads to two important results. First, it establishes an equivalence between convergent fuzzy CA and the mean field approximation on Boolean CA, an estimation of their asymptotic density. Second, we show that the density conservation property, extensively studied in the Boolean domain, is preserved in the fuzzy domain: a Boolean CA is density conserving if and only if the corresponding FCA is sum preserving. A similar result is established for another novel “spatial” density conservation property. Finally, we prove an interesting parallel between additivity of Boolean CA and oscillation of the corresponding fuzzy CA around its fixed point. In fact, we show that a Boolean CA has a certain form of additivity if and only if the behavior of the corresponding fuzzy CA around its fixed point coincides with the Boolean behavior. These connections between the Boolean and the fuzzy models are the first formal proofs of a relationship between them.
21
Theory of Self-Reproducing Automata
Jacob T. Schwartz, John von Neumann, Arthur W. Burks · Mathematics of Computation · 1967 · 5.5K citations
Theory and Applications of Cellular Automata
Stephen Wolfram · 1986 · 1.7K citations
Cellular automata and complexity: collected papers
Choice Reviews Online · 1994 · 379 citations
Number-conserving cellular automaton rules
Nino Boccara, Henryk Fukś · arXiv (Cornell University) · 1999 · 88 citations · Full text