Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2002

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Formal language recognition by stochastic cellular automata

Merkle D., Worsch T.

Fundamenta Informaticae

2002

Vol. 52, nr 1-3

183-201

We present two generalizations of cellular automata where transitions from one configuration to the next are no longer deterministic but depend on some element of randomization. The main topic is a model which not only takes into account the probabilities of cells being in certain states but also their dependencies. It formalizes the approach of ``randomized simulations'' often used for the modeling of real phenomena. In this paper the power of stochastic CA as language recognizers is investigated. Generalizations of well-known tools (stochastic signals and product automata) are used to prove that stochastic CA are strictly more powerful than deterministic CA and stochastic finite automata (which are known to recognize uncountably many languages).