Wyniki wyszukiwania - Biblioteka Nauki

1

Limit Sets of Stable and Unstable Cellular Automata

100%

Ballier A. , Guillony P. , Kari J.

Fundamenta Informaticae

|

2011

|

tom Vol. 110, nr 1-4

45-56

EN

We construct a cellular automaton (CA) with a sofic and mixing limit set and then construct a stable CA with the same limit set, showing there exist subshifts that can be limit sets of both stable and unstable CAs, answering a question raised by A. Maass.

2

Cellular Automata, Decidability and Phasespace

100%

Sutner K.

Fundamenta Informaticae

|

2010

|

tom Vol. 104, nr 1/2

141-160

EN

Cellular automata have rich computational properties and, at the same time, provide plausible models of physics-like computation. We study decidability issues in the phasespace of these automata, construed as automatic structures over infinite words. In dimension one, slightly more than the first order theory is decidable but the addition of an orbit predicate results in undecidability. We comment on connections between this "what you see is what you get" model and the lack of natural intermediate degrees.

3

On the circuit depth of structurally Reversible Cellular Automata

63%

Kari J.

Fundamenta Informaticae

|

1999

|

tom Vol. 38, Nr 1,2

93-107

EN

We study the family of structurally reversible cellular automata that use the (generalized) Margolus neighborhoods. We show that every reversible cellular automaton (RCA) can be embedded into the standard two layer Margolus neighborhood defined by two overlapping square partitions of the cellular space and two one-to-one local rules. The embedding allows step-by-step simulations. Then we investigate how many layers of one-to-one local rules are required in exact representations of RCA. We show how in the d-dimensional cellular space any consecutive d+2 layers can be combined into d+1 layers. This proves that no more than d+1 layers are necessary. We demonstrate that in the two-dimensional case d=2 the number d+1 is optimal by providing an example of an RCA with three layers of local rules that cannot be expressed in two layers.

4

A New Time-Optimum Synchronization Algorithm for Rectangle Arrays

63%

Umeo H. , Uchino H.

Fundamenta Informaticae

|

2008

|

tom Vol. 87, nr 2

155-164

EN

The firing squad synchronization problem on cellular automata has been studied extensively for more than forty years, and a rich variety of synchronization algorithms have been proposed so far. In the present paper, we propose a new optimum-time algorithm for synchronizing two-dimensional cellular automata. The algorithm can synchronize any two-dimensional rectangle array of size m ×n in optimum m + n + max(m, n)- 3 steps. A partial implementation of the algorithm for small cellular arrays is also given.

5

A Geometrical Hierarchy on Graphs via Cellular Automata

63%

Martin B.

Fundamenta Informaticae

|

2002

|

tom Vol. 52, nr 1-3

157-181

EN

Historically, cellular automata were defined on the lattices \mathbbZn, but the definition can be extended to bounded degree graphs. Given a notion of simulation between cellular automata defined on different structures (namely graphs of automata), we can deduce an order on graphs. In this paper, we link this order to graph properties and explicit the order for most of the common graphs.

6

Cellular Automata: Energy Consumption and Physical Feasibility

63%

Sanders P. , Vollmar R. , Worsch T.

Fundamenta Informaticae

|

2002

|

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

7

Formal language recognition by stochastic cellular automata

63%

Merkle D. , Worsch T.

Fundamenta Informaticae

|

2002

|

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

8

Three-dimensional Cellular Automata for Reaction-Diffusion Systems

63%

Weimar J. R.

Fundamenta Informaticae

|

2002

|

tom Vol. 52, nr 1-3

277-284

EN

Cellular automata for reaction-diffusion systems are efficient enough to make the simulation of large three-dimensional systems feasible. The principal construction mechanisms used here are not much different from those for two-dimensional cellular automata. Diffusion is realized through a local averaging, and all the nonlinear reaction terms are collected in a table-lookup. The special issue in three dimensions is the need to increase time- and space- scales as much as possible to achieve sufficient system sizes. This can be done through the use of numerical integration schemes for constructing the lookup table, and through the use of special diffusion operators. We present examples of complex three-dimensional behaviors in an excitable reaction-diffusion system and in a model of a pattern-forming chemical reaction.

9

Chaotic Subshifts and Related Languages Applications to one-dimensional Cellular Automata

63%

Cattaneo G. , Dennunzio A. , Margara L.

Fundamenta Informaticae

|

2002

|

tom Vol. 52, nr 1-3

39-80

EN

Subshift behaviors of one-dimensional (1D) bi-infinite Cellular Automata are studied. In particular the conditions under which subshifts generated by CA 1D dynamical systems exhibit some components of the chaotic behavior (in particular transitivity, topological mixing and strong transitivity) are investigated. A complete classification of all elementary (Boolean radius one) CA with respect to subshifts is given.

10

Synchronization of a line of identical processors at a given time

63%

La Torre S. , Napoli M. , Parente D.

Fundamenta Informaticae

|

1998

|

tom Vol.34, nr 1,2

103-128

EN

We are given a line of n identical processors (finite automata) that work synchronously. Each processor can transmit just one bit of information to the adjacent processor (if any) to the left and to the right. The computation starts at time 1 with the leftmost processor in an initial atate and all other processors in a quiescent state. Given the time f(n), the problem is to set (synchronize) all the processors in a particular state for the first time, at the very same instant f(n). This problem is also known as the Firing Squad Synchronization Problem and was introduced by Moore in 1964. Mazoyer has given a minimal time solution with the least number of different states (six) and very recently he has given a minimal time solution for the constrained problem in which adjacent processors can exchange only one bit. In this paper we present solutions that synchronize the line a given time, expressed as a function of n. In particular we give solutions that synchronize at the times n log n, nÖn, n2 and 2n. Moreover we also show how to compose solutions in such a way to obtain synchronizing solutions for all times expressed by polynomials with nonnegative coefficients. Clearly all such solutions work also in the general case when the bit constraint is relaxed.

11

Cellular Automata and Self-Adaptive hp Finite Element Method Multi-Component Diffusion Models

63%

Paszyńska A. , Paszyński M.

Computer Methods in Materials Science

|

2009

|

tom Vol. 9, No. 2

221-227

PL

W artykule zaprezentowany został przegląd opracowanych modeli dyfuzji wieloskładnikowej. Problem dyfuzji wieloskładnikowej opisany został za pomocą modeli stochastycznych, bazujących na automatach komórkowych, jak również modeli ciągłych, bazujących na równaniach różniczkowych cząstkowych. Rozważane modele stochastyczne opierają się na automatach komórkowych z regułami wymiany lub rotacji cząstek wielofazowych. Podczas symulacji, cząstki różnych faz poddawane są rotacji zgodnie lub przeciwnie do ruchu wskazówek zegara, zgodnie z przyjętym prawdopodobieństwem. Współczynnik dyfuzji symulowanego układu cząstek definiowany jest poprzez modyfikację prawdopodobieństw wykonania reguł międzycząsteczkowych. Opracowane modele zostały zweryfikowane poprzez wykonanie szeregu symulacji numerycznych, oraz porównane do uprzednio opracowanych modeli ciągłych, bazujących na adaptacyjnej metodzie elementów skończonych.

EN

The paper presents a survey of developed multi-component diffusion models. Stochastic and continuous PDE models for multi component diffusion problems are studied by performing a sequence of numerical simulations. The stochastic models are based on Cellular Automata with interchange and block-rotation model. The multi-component particles are either intechanged or rotated clockwise or counter-clockwise with prescribed probability. The resulting diffusion coefficients are obtained by statistical tools, and can be modified by adjusting the probabilities of interchange or rotations. The continuous PDE models are based on classical variational formulations solved by the self-adaptive hp Finite Element Method. Numerical results are compared and discussed.

12

On Expansivity and Pseudo-Orbit Tracing Property for Cellular Automata

51%

Jalonen J. , Kari J.

Fundamenta Informaticae

|

2020

|

tom Vol. 171, nr 1-4

239--259

EN

Ultimate expansivity extends concepts of expansivity and positive expansivity. We consider one-sided variants of ultimate expansivity and pseudo-orbit tracing property (also known as the shadowing property) for surjective one-dimensional cellular automata. We show that ultimately right (or left) expansive surjective cellular automata are chain-transitive; this improves a result by Boyle that expansive reversible cellular automata are chain-transitive. We then use this to show that left-sided pseudo-orbit tracing property and right-sided ultimate expansivity together imply pseudo-orbit tracing property for surjective cellular automata. This reproves some known results, most notably some of Nasu’s. Our result improves Nasu’s result by dropping an assumption of chain-recurrence, however, we remark that this improvement can also be achieved using the Poincaré recurrence theorem. The pseudo-orbit tracing property implies that the trace subshifts of the cellular automaton are sofic shifts. We end by mentioning that among reversible cellular automata over full shifts we have examples of right expansive cellular automata with non-sofic traces, as well as examples of cellular automata with left pseudo-orbit tracing property but non-sofic traces, illustrating that neither assumption can be dropped from the theorem mentioned above. This paper is a generalized and improved version of a conference paper presented in AUTOMATA 2018.

13

Cellular automata approach to task scheduling

51%

Święcicka A. , Seredyński F.

Studia Informatica : systems and information technology

|

2003

|

tom Vol. 1(1)

37--46

EN

In this paper we propose using cellular automata (CAs) to perform distributed scheduling tasks of a parallel program in the two processor system. We consider a program graph as a CA with elementaty cells interacting locally according to a certain rule which must be found. Effective rules for a CA are discovered by a genetic algorithm (GA). With these rules, CA-based scheduler is able to find allocations which minimize the total execution time of the program in the two processor system. We also show a possibility of reusing knowledge gained during solving instances of the scheduling problem. Keywords: cellular automata, genetic algorithms, scheduling problem.

14

Some Applications of Cellular Automata in Learning Systems Constructions

51%

Borkowski P.

Scientific Issues of Jan Długosz University in Częstochowa. Mathematics

|

2005

|

tom Vol. 10

5--16

EN

Today the von Neumann invention of cellular automata is one of import and tools of artificial intelligence research. Cellular automata show their usage in simultaneous calculations, creating data bases and simulating physical processes. The goal of this article is an introduction to the learning system called CELLS, which marnner of work is directly connected with the cellular automata evolution rules.

15

Influence of a Range of Interaction among Agents on Efficiency and Effectiveness of Knowledge Transfer within an Organisation

51%

Paradowski K. , Kowalska-Styczeń A. , Malarz K.

Acta Physica Polonica A

|

2018

|

tom 133

|

nr 6

1470-1476

EN

In this study we examined how the size of non-formal groups between organisation members affect the transfer of knowledge in the context of the efficiency and effectiveness of this process. To analyse the dynamics of the transfer of knowledge the cellular automata model was used. The model is based on local interactions between members of the organisation, that take place in the nearest neighbourhood. These groups of close neighbours are represented by von Neumann's neighbourhood (four nearest-neighbours) and Moore's neighbourhood (four nearest-neighbours and four next-nearest neighbours) and complex neighbourhood (four nearest neighbours, four next-nearest neighbours and four next-next-neighbours). The results of the simulation show the influence of the size of the neighbourhood on the efficiency of knowledge transfer.

16

Cellular automata: structures and some applications

51%

Burzyński M. , Cudny W. , Kosiński W.

Journal of Theoretical and Applied Mechanics

|

2004

|

tom Vol. 42 nr 3

461-482

EN

A new approach to the modelling of various nature phenomena such as predator and prey ecological system, heat transport, spreading of oil slick and traffic flow is introduced. Cellular automata (CA) are discrete dynamical systems whose behaviour is completely specified in terms of simple local relations. They are mathematical models of spatialy distributed processes; however they can lead to an appropriate simulation of comlex dynamic processes. Applications to heat transfer and problems of environmental simulations are done. A discrete automaton model with fuzzy rules to simulate one-way traffic flow is also described. Results of simulations are consistent with phenomena observed in reality. It gives a base to propose the cellular automata tool as an option in modelling and solving problems of complex (and some times, not completely known) nature.

PL

W pracy zaprezentowano metodę modelowania układów i zjawisk obserwowanych w przyrodzie, takich jak dynamika systemu ekologicznego drapieżnik-ofiara, przewodzenie ciepła, rozprzestrzenianie się plamy ropy naftowej po wycieku na wodzie czy ruch strumienia pojazdów na drodze miejskiej. Metodę oparto na tzw. automatach komórkowych, które są układami dyskretnymi o zachowaniach ściśle zdeterminowanych prostymi relacjami o charakterze lokalnym. Automaty komórkowe to matematyczne modele procesów przestrzennych, mogące z powodzeniem opisywać złożone zjawiska dynamiczne. W pracy przedstawiono aplikację do zagadnienia przewodzenia ciepła oraz kilku symulacji środowiskowych. Przedstawiono także model automatowy z regułami rozmytymi opisujący jednokierunkowy ruch pojazdów na drodze. Wyniki symulacji okazały się zgodne z obserwacjami rzeczywistych układów. Zachęcające rezultaty badań skłaniają do postrzegania automatów komórkowych jako efektywnej opcji w modelowaniu i rozwiązywaniu problemów o złożonej (czasem nie całkiem rozpoznanej) naturze.

17

Periodic Orbits and Dynamical Complexity in Cellular Automata

51%

Dennunzio A. , Di Lena P. , Formenti E. , Margara L.

Fundamenta Informaticae

|

2013

|

tom Vol. 126, nr 2-3

183--199

EN

We investigate the relationships between dynamical complexity and the set of periodic configurations of surjective Cellular Automata. We focus on the set of strictly temporally periodic configurations, i.e., the set of those configurations which are temporally but not spatially periodic for a given surjective automaton. The cardinality of this set turns out to be inversely related to the dynamical complexity of the cellular automaton. In particular, we show that for surjective Cellular Automata, the set of strictly temporally periodic configurations has strictly positive measure if and only if the cellular automaton is equicontinuous. Furthermore, we show that the set of strictly temporally periodic configurations is dense for almost equicontinuous surjective cellular automata, while it is empty for the positively expansive ones. In the class of additive cellular automata, the set of strictly temporally periodic points can be either dense or empty. The latter happens if and only if the cellular automaton is topologically transitive. This is not true for general transitive Cellular Automata, where the set of of strictly temporally periodic points can be non-empty and non-dense.

18

Remarks on the Critical Behavior of Second Order Additive Invariants in Elementary Cellular Automata

51%

Fukś H.

Fundamenta Informaticae

|

2007

|

tom Vol. 78, nr 3

329-341

EN

We present results of some numerical investigations of second order additive invariants in elementary cellular automata rules. Fundamental diagrams of rules which possess additive invariants are either linear or exhibit singularities similar to singularities of rules with first-order invariant. Only rules which have exactly one invariants exhibit singularities. At the singularity, the current decays to its equilibrium value as a power law ta, and the value of the exponent a obtained from numerical simulations is very close to -1/2. This is in agreements with values previously reported for number-conserving rules, and leads to a conjecture that regardless of the order of the invariant, exponent a has a universal value of 1/2.

19

Numerical investigation of the static recrystallization inhomogeneities across the plate thickness during continuous annealing

51%

Sitko M. , Madej Ł. , Perzyński K. , Kwiaton N. , Kuziak R. , Radwański K.

Computer Methods in Materials Science

|

2015

|

tom Vol. 15, No.3

371--379

EN

Analysis of static recrystallization inhomogeneities along the thickness of the cold rolled ferritic-pearlitic steel during continuous annealing process is the main goal of the present paper. The multiscale concurrent Cellular Automata Final Element (CAFE) model is used during the numerical investigation. The general concept of the CA algorithm of static recrystallization phenomenon is evaluated. The multiscale model of cold rolling based on the digital material representation (DMR) concept is used to accurately predict deformation energy distribution along the microstructure features and provide input data for the CA model. The final material morphology and recrystallization volume fractions after recrystallization in different plate locations: near the surface, in the middle of a plate, respectively, are evaluated. Finally, examples of obtained results of recrystallized microstructures are compared with the experimental data, to validate the approach.

PL

Celem niniejszej pracy jest analiza numeryczna niejednorodności rozwoju mikrostruktury na grubości pasma stali ferrytyczno-perlitycznej podczas ciągłego wyżarzania. W pracy wykorzystano bieżny model wieloskalowy na bazie metody elementów skończonych połączonej z metodą automatów komórkowych ( Cellular Automata Finał Element - CAFE). Model wieloskalowy walcowania na zimno oparto na idei cyfrowej reprezentacji materiału do dokładnego określenia energii zmagazynowanej w materiale w wyniku odkształcenia plastycznego, która zostanie wykorzystana jako jeden z parametrów początkowych modelu automatów komórkowych.Następnie przedstawiono wyniki w postaci morfologii materiału wraz z odpowiadającymi ułamkami części zrekrystalizowanej po procesie nagrzewania odpowiednio: przy powierzchni oraz w środku płyty. Uzyskane wyniki obliczeń numerycznych zostały porównane z danami eksperymentalnymi w celu walidacji modelu.

20

Image reconstruction with the use of evolutionary algorithms and cellular automata

51%

Seredyński F. , Skaruz J. , Piraszewski A.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2012

|

tom Vol. 12, no. 4

39--49

EN

In the paper we present a new approach to the image reconstruction problem based on evolution algorithms and cellular automata. Two-dimensional, nine state cellular automata with the Moore neighbourhood perform reconstruction of an image presenting a human face. Large space of automata rules is searched through efficiently by the genetic algorithm (GA), which finds a good quality rule. The experimental results show that the obtained rule allows to reconstruct an image with even 70% damaged pixels. Moreover, we show that the rule found in the genetic evolution process can be applied to the reconstruction of images of the same class but not presented during the evolutionary one.