Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: sequential machine theory

Sortuj według:

Ogranicz wyniki do:

Grigorieff S., Margenstern M.

Fundamenta Informaticae

2004

Vol. 61, nr 1

19--27

In this paper, we consider cellular automata on special grids of the hyperbolic plane: the grids are constructed on infinigons, i.e. polygons with infinitely many sides. We show that the truth of arithmetical formulas can be decided in finite time with infinite initial recursive configurations. Next, we define a new kind of cellular automata, endowed with data and more powerful operations which we call register cellular automata. This time, starting from finite configurations, it is possible to decide the truth of arithmetic formulas in linear time with respect to the size of the formula.

Integrating Forms of Interaction in a Distributed Model

Bandini S., Simone C.

Fundamenta Informaticae

2004

Vol. 61, nr 1

1--17

The main aim of this paper is to present the formal description of the Multilayered Reaction-Diffusion Machine (MRDM, an extension of a previously introduced RDM, Reaction-Diffusion Machine) which can be seen as a generalization of Cellular Automata since it relaxes some constraints on uniformity, locality and closure. The MRDM offers a formal and computational environment where to describe, represent and simulate coordination models which explicitly require spatial features to be considered and integrates different forms of interaction. The paper is divided into two main parts. In the first one, the formal description of the MRDM is presented. In the second part the MRDM is put in relation with deterministic Turing machines; moreover we show how the MRDM, under determined constraints, collapses on a traditional CA.

Almost Periodic Configurations on Linear Cellular Automata

Sutner K.

Fundamenta Informaticae

2003

Vol. 58, nr 3,4

223--240

We study computational properties of linear cellular automata on configurations that differ from spatially periodic ones in only finitely many places. It is shown that the degree structure of the orbits of cellular automata is the same on these configurations as on the space of finite configurations. We also show that it is undecidable whether the cellular automaton exhibits complicated behavior on configurations of sufficiently long spatial periods and exhibit cellular automata with undecidable orbits whose orbits on backgrounds of all fixed sizes are decidable.