Wyniki wyszukiwania - BazTech

1

On Completeness and Decidability of Phase Space Invertible Asynchronous Cellular Automata

Wacker S., Worsch T.

Fundamenta Informaticae

|

2013

|

Vol. 126, nr 2-3

157--181

EN

While for synchronous deterministic cellular automata there is an accepted definition of reversibility, this is not the case for asynchronous cellular automata. We first discuss a few possibilities and then investigate what we call phase space invertible asynchronous cellular automata. We will show that for each Turing machine there is a phase space invertible purely asynchronous cellular automaton simulating it and that it is decidable whether an arbitrary-dimensional purely and a one-dimensional fully asynchronous cellular automaton is phase space invertible.

2

Simulations Between Cellular Automata on Trees Extended by Horizontal Edges

Worsch T.

Fundamenta Informaticae

|

2003

|

Vol. 58, nr 3,4

241--260

EN

In this paper we consider cellular automata where the graph defined by the neighbourhood relations between the cells is a tree ``with additional edges''. This includes hyperbolic CA defined by regular tessellations of the two-dimensional hyperbolic plane. It is shown that all X-tree CA and all hyperbolic CA can C-simulate each other with constant slowdown, independent of the ``branching factors'' of the underlying trees.

3

Formal language recognition by stochastic cellular automata

Merkle D., Worsch T.

Fundamenta Informaticae

|

2002

|

Vol. 52, nr 1-3

183-201

EN

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).

4

Cellular Automata: Energy Consumption and Physical Feasibility

Sanders P., Vollmar R., Worsch T.

Fundamenta Informaticae

|

2002

|

Vol. 52, nr 1-3

233-248

EN

Using cellular automata as models of parallel machines we investigate constraints for the energy consumption of r-dimensional machines which are motivated by physical limitations for the case r = 3. Depending on the operations which must be considered to dissipate energy, some relations between the relative performance of 2-dimensional and 3-dimensional machines are derived. In the light of these results it seems imperative that for feasible models of computation energy consumption has to be considered as an additional complexity measure.