Wyniki wyszukiwania - Biblioteka Nauki

1

Cellular Automata, Decidability and Phasespace

100%

Sutner K.

|

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.

2

A New Time-Optimum Synchronization Algorithm for Rectangle Arrays

63%

Umeo H. , Uchino H.

|

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.

3

On the circuit depth of structurally Reversible Cellular Automata

63%

Kari J.

|

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

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.

5

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.

6

Some Applications of Cellular Automata in Learning Systems Constructions

51%

Borkowski P.

|

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.

7

Cryptosystem Based on Reversible Two-dimensional Cellular Automata

51%

Wiśniewski A.

Studia Informatica : systems and information technology

|

2009

|

tom Vol. 2(13)

97--105

EN

Cellular Automata have been successfully applied to several scientific problems such as among others image processing or data encryption. One could find reversibility of dynamics is a fundamental feature of nature. While the most CA are not reversible in nature, one can find some CA with simple behavior could be reversible. Reversible cellular automata (RCA) as efficient encryption and decryption devices was originally conceived by Kari. In this introduction paper, we analyze and develop reversible cellular automata (RCA) based on Kari’s idea and some Clarridge’s concepts.

8

Computer modelling of pentoxifylline release from a cylinder-shaped hydroxylapatite carrier

51%

Mietła A. , Mycek B. , Wanat I. , Wąs J. , Zima A.

|

2012

|

tom Vol. 8, no. 1

89--109

EN

The main objective of this article is to present the basic stages of creating a computer simulation of medication release from an undegraded carrier. Additionally, an innovative approach was presented to the construction of a porous material used for making the carrier for the medication. The programme presented here is based on Cellular Automata, used as a tool for modelling physical, chemical and biological phenomena which change in time. The results of in-silico calculations have been compared with empirical results.

9

Capturing local material heterogeneities in numerical modelling of microstructure evolution

51%

Madej L. , Sitko M. , Fular A. , Sarzyn R. , Werminski M. , Perzynski K.

|

tom Vol. 21, No. 4

29--48

EN

The work focuses on developing the complex digital shadow of the metallic material microstructure that can predict its evolution during metal forming operations. Therefore, such a digital shadow has to consider all major physical mechanisms influencing the particular investigated phenomenon. The motivation for the work is directly related to the development of modern metallic materials, often of multiphase nature. Such microstructure types lead to local heterogeneities influencing material behaviour and eventually macroscopic properties of the final product. The concept of the digital material shadow, stages of the model development, and examples of practical applications to simulation of microstructure evolution are presented within the work. Capturing local heterogeneities that have a physical origin and eliminating numerical artefacts is particularly addressed. Obtained results demonstrate the capabilities of such a digital microstructure shadow approach in the numerical design of final product properties.

10

Modified Traffic Cellular Automaton for the Density Classification Task

51%

Kari J. , Le Gloannec B.

|

2012

|

tom Vol. 116, nr 1-4

141-156

EN

The density classification task asks to design a cellular automaton that converges to the uniform configuration that corresponds to the state that is in majority in the initial configuration. We investigate connections of this problem to state-conserving cellular automata. We propose a modified traffic CA that washes out finite islands in the same way as the Gacs, Kurdyumov and Levin automaton, but is also guaranteed to converge to a uniform configuration on rings of odd size. We find experimentally several good classifiers that are close to state-conserving cellular automata, and we observe that the best performing known density classifier by Wolz and de Oliveira is only a simple swap away from a state-conserving automaton.

11

Animation of group of elastic objects based on distributed physical simulation

51%

Wcisło R. , Kitowski J. , Mościński J.

|

tom Vol. 7, No. 1/2

41-48

EN

The paper presents the overview of a computer system for performing animation of a set solids and (optinally) a liquid medium. The animation is driven by the simulation mbased on physical laws to ensure the maximum reality.

12

RCAFE Based Numerical Model of Dynamic Recrystallization

51%

Legwand A. , Sitko M. , Perzyński K. , Madej Ł.

|

2016

|

tom Vol. 16, No. 2

52--60

EN

The main goal of the paper is dedicated to proper arrangement of the Finite Element (FE) and Random Cellular Automata (RCA) methods in order to develop numerical model of dynamic recrystallization (DRX) and therefore to simulate microstructure morphology changes during plastic deformation at elevated temperatures. In the approach, Finite Element solver provides information on equivalent stress and strain fields after subsequent time steps. Then these data are transferred to RCA model, which is responsible for evaluation of corresponding microstructure morphology evolution and dislocation density changes. Finally, information from the CA part is send back to the FE solver as an input for the next time step. As a result, a fully coupled RCAFE model to simulate progress of DRX is established. The present paper is directly focused on development of algorithms and methods to transfer input/output data between both FE and RCA models. The developed communication protocol is based on the Abaqus VUMAT subroutine. Examples of obtained results from the developed model are also presented to highlight its potential.

13

Efficient cellular automata model for prediction of damage of hot forging tools due to thermal fatigue

51%

Nowak P. , Rauch Ł.

|

tom Vol. 14, No. 4

197--205

EN

W pracy przedstawiono implementację modelu automatów komórkowych (ang. Cellular Automata - CA) przewidującego rozwój pękania zmęczeniowego w narzędziach do kucia na gorą¬co. Reguły przejścia opracowano na bazie dostępnych informacji dotyczących inicjacji i propagacji pęknięć. Współczynniki modelu wyznaczono na podstawie prób zmęczeniowych przeprowadzo¬nych na symulatorze Gleeble 3800. Model CA połączono z pro¬gramem MES, który symuluje naprężenia podczas kucia. To wieloskalowe podejście jest bardzo wymagające obliczeniowo. Dlatego efektywna równoległa implementacja tego modelu była głównym celem pracy. Model pękania zmęczeniowego zrealizowano w technice GPGPU, co ułatwiło implementację algorytmów za pomocą udostępnienia API (z j. ang. Application Programming Interface) dostarczającego funkcje z biblioteki OpenGL. Platformę wspoma-gającą obliczenia CA podzielono na części biblioteczną i aplika¬cyjną. Biblioteka dostarcza API do obsługi jądra programu w technologii OpenGL dedykowanego na akceleratory oblicze¬niowe CPU i GPU. Aplikacyjna część wykorzystuje API dostar¬czone przez bibliotekę i jej zadaniem jest przekazanie i zarządza¬nie parametrami wejściowymi do obliczeń. Zadaniem aplikacji jest również stworzenie wejściowej przestrzeni automatów ko¬mórkowych, wczytanie i ustawienie wartości wewnętrznych komórek CA oraz przekazanie ich do obliczeń na akceleratorach. W pracy opisano implementację modelu oraz przedstawiono przykładowy wynik symulacji pęknięć w matrycy kuźniczej. Dzięki zrównolegleniu algorytmu i wykorzystaniu czterech kart GPU uzyskano wysokie przyspieszenie obliczeń przy dobrej skalowalności.

14

Stochastic cellular automata modeling of excitable systems

51%

Szakály T. , Lagzi I. , Izsák F. , Roszol L. , Volford A.

|

nr 4

471-486

EN

A stochastic cellular automaton is developed for modeling waves in excitable media. A scale of key features of excitation waves can be reproduced in the presented framework such as the shape, the propagation velocity, the curvature effect and spontaneous appearance of target patterns. Some well-understood phenomena such as waves originating from a point source, double spiral waves and waves around some obstacles of various geometries are simulated. We point out that unlike the deterministic approaches, the present model captures the curvature effect and the presence of target patterns without permanent excitation. Spontaneous appearance of patterns, which have been observed in a new experimental system and a chemical lens effect, which has been reported recently can also be easily reproduced. In all cases, the presented model results in a fast computer simulation.

15

An Algorithmic Approach to Tilings of Hyperbolic Spaces: Universality Results

51%

Margenstern M.

Fundamenta Informaticae

|

2015

|

tom Vol. 138, nr 1/2

113--125

EN

In this paper, our results on algorithmic analysis of tiling in hyperbolic spaces are discussed. We overview results and developments obtained by the approach, focusing on the construction of universal cellular automata in hyperbolic spaces with a minimal number of cell states.

16

Modelling of brittle damage nucleation by means of

51%

Nowak K.

|

tom Vol. 7, No. 1

150-155

EN

The main goal of the paper is to motivate damage nucleation in metals, subjected to creep conditions, on the level of material structure. In classical approach of mechanics it is achieved by introducing a scalar (or tensorial) parameter called damage variable and postulating its phenomenological evolution equation. Such an approach has been successfully used in analysis of structures under different loading circumstances, giving rise to the formation of special branch of mechanics “Continuum Damage Mechanics” (CDM). This approach reflects neither physical process that is underlying macroscopically observed phenomena, nor material structure. On the other hand, in metallurgy, the process of brittle damage formation is well recognized and described. In brief, it consists of microcraking and voids formation initiating in the triple-points and developing along grain boundaries. Therefore, it is essential to associate any description of damage formation with modelling of material structures. In the paper, it was achieved by associating deformation process with changing states of CA cells. To model time dependent behaviour of representative volume element (RVA) of material a 3D cellular automaton was developed. The process of damage formation consists of two steps in each time increment. In the first one, the tension (or compression) of RVE over an increment of deformation mesh was supposed, and then projected onto cellular automaton cells. In the second step the damage formation is controlled by the rules of an automaton. These probabilistic rules change the state of mass cell to empty for specific combination of neighbouring cells, provided this cell corresponds to grain boundary. Above procedure allows to forms microvoids or microcracs. The main rule governing cellular automaton is the mass conservation law, which enforced the number of empty cells in RVE. As the outcome from CA the damage variable is calculated as a percentage of entire damage of RVE. The entire damage is assumed to happen when the voids form a surface spanning two opposite borders of element. The procedures developed in the paper are used to modify standard FE programs through incorporating results of CA-based microstructural analysis according to the CAFE methodology. For each Gauss point of finite element the CA is running and values of state variables are exchanged between FE and CA. Strains obtained from FE are used to calculate deformation of the borders of RVE. In turn, the damage variable calculated from CA modifies the value of stress used in FE solution. In such a way multiscale description of phenomenon is proposed to obtain solution of engineering problems with sound physical background. As an example, a plate under uniform pressure working in creep condition is analysed using HKS Abaqus. Results obtained are compared with numerical solution of CDM.

PL

Zaproponowano opis nukleacji uszkodzeń dla metali pracujących w warunkach pełzania na poziomie mikrostruktury. Opisując to zjawisko w klasycznym podejściu do mechaniki wprowadza się skalarny (lub tensorowy) parametr nazywany uszkodzeniem i postuluje fenomenologiczne prawo jego rozwoju. Takie podejście jest z powodzeniem używane w analizie konstrukcji w różnych warunkach obciążenia tworząc specjalną gałąź mechaniki zwaną kontynualną mechaniką uszkodzeń. Pomimo rozwiązania szeregu ważnych technicznych problemów, takich jak oszacowanie czasu do pojawienia się pierwszego makroskopowego uszkodzenia a także dalszego rozwoju procesu pękania, podejście to nie odzwierciedla ani procesu fizycznego leżącego u podstaw makroskopowo obserwowanych zjawisk, ani struktury materiału. W niniejszej pracy proponuje się podejście wieloskalowe poprzez połączenie rozwiązania numerycznego na poziomie makroskopowym z opisem zachowania się struktury materiału na poziomie mikro przy pomocy automatów komórkowych. Otrzymane rozwiązania porównane

17

Some aspects which deny a use of 2D cellular automata for modelling of recrystallization

51%

Svyetlichnyy D.

|

tom Vol. 7, No. 1

182-188

EN

The main reason why the two-dimensional cellular automata (2D CA) are preferred to the three-dimensional (3D) ones is time of calculations. A number of cells in the 2D CA is the second power of space size, while in the 3D CA it is the third power. It pertains to a number of neighboring cells as well. Then the cost of the 3D calculation is higher than that of the 2D calculation more than the space size of the CA. It means that simulation in the 3D CA of the linear size of 100 cells demands more calculations than 100 simulations in the 2D CA of the same size. The CA is used for modeling of crystallization, recrystallization, phase transforrnation, crack propagation, micro-shear band and shear band propagation. But can the 2D CA hold up a mirror to the real process? In the paper some aspects of the using of the 2D CA for the recrystallization are considered. Four main problems, which can be solved or at least can be accounted, are dealt with here. Those arę kinetics of the recrystallization, a nucleation, a grain growth rate and deformation of grains. Some of the problem can be solved for the static recrystallization but not for the dynamic one. Some proposals and recommendation are included in the paper.

PL

Czas obliczeń jest głównym czynnikiem dającym preferencję zastosowań rozwiązania 2D w porównaniu z 3D. Liczba komórek w przestrzeni 2D jest kwadratem tej przestrzeni, a w 3D jest to trzecia potęga. Zwiększa to również liczbę sąsiadów danej komórki. W konsekwencji czas obliczeń 3D jest dłuższy więcej razy, niż wynikałoby to tylko z rozmiaru przestrzeni. Automaty komórkowe są powszechnie używane do modelowania krystalizacji, rekrystalizacji, przemian fazowych, propagacji pęknięć, rozwoju mikropasm i pasm ścinania itp. Powstaje pytanie czy rozwiązanie 2D może oddać poprawnie realny proces? W artykule opisano pewne aspekty zastosowania rozwiązania 2D do opisu rekrystalizacji. Rozważono cztery problemy, które mogą być rozwiązane lub chociaż przeanalizowane. Są to kinetyka rekrystalizacji, zarodkowanie, wzrost ziaren i odkształcenie ziaren. Niektóre z tych problemów mogą być rozwiązywane tylko dla statycznej rekrystalizacji. W pracy przedstawiono pewne propozycje i rekomendacje w tym zakresie.

18

Problem of the artificial anisotropy in solidification modeling by cellular automata method

51%

Burbelko A. , Kapturkiewicz W. , Gurgul D.

|

tom Vol. 7, No. 1

182-188

EN

Modeling of the dendritic growth in the mesoscale with a cellular automaton takes into account the temperature of the thermodynamic equilibrium as a function of the local concentration and mass diffusion, heat transfer and local temperature, surface energy and curvature of the grain boundaries. Unfortunately, most of the previous solutions produce artificial symmetry of simulation results. This symmetry reflects the anisotropy of the CA computational grid, rather than the properties of the modeled substance. The method of the accuracy ranking estimation proposed in this paper for known methods of solidification rate calculation. The best solution has been chosen with the highest precision and minimal artificial anisotropy of the simulation results.

PL

Modelowanie krystalizacji ziaren dendrytycznych z wykorzystaniem automatów komórkowych (AK) pozwala uwzględnić szereg zjawisk: zmianę temperatury równowagi termodynamicznej na granicy faz pod wpływem zmiany lokalnego składu chemicznego w wyniku redystrybucji i dyfuzji składników, przepływ ciepła, wpływ krzywizny granicy międzyfazowej i jej energii powierzchniowej. Niestety, większość ze znanych dotychczas rozwiązań generuje sztuczną symetrię wyników modelowania, która odzwierciedla w większym stopniu anizotropię stosowanej siatki obliczeniowej, aniżeli właściwości modelowanych substancji. W pracy udowodniono, że przyczyny sztucznej symetrii mają związek ze stosowanymi metodami obliczenia szybkości przemiany fazowej i kierunku migracji granicy między fazowej. Przedstawiono sposób wyznaczania ocen dokładności tych metod. Na postawie opracowanej procedury oceny wybrano metody i równania, zapewniające najwyższą precyzję i minimalny poziom sztucznej anizotropii wyników modelowania.

19

Simulation of dynamic recrystallization using random grid cellular automata

51%

Yazdipour N. , Davies C. , Hodgson P.

|

tom Vol. 7, No. 1

175-181

EN

Computer simulation is a powerful tool to predict microstructure and its evolution in dynamic and post-dynamic recrystallization. CAFE proposed as an appropriate approach by combining finite element (FE) method and cellular automata (CA) for recrystallization simulation. In the current study, a random grid cellular automaton (CA), as micro-scale model, based on finite element (FE), as macro-scale method, has been used to study initial and evolving microstructural features; including nuclei densities, dislocation densities, grain size and grain boundary movement during dynamic recrystallization in a C-Mn steel. An optimized relation has been established between mechanical variables and evolving microstructure features during recrystallization and grain growth. In this model, the microstructure is defined as cells located within grains and grain boundaries while dislocations are randomly dispersed throughout microstructure. Changes of dislocation density during deformation are described considering hardening, recovery and recrystallization. Recrystallization is assumed to initiate near grain boundaries and nucleation rate was considered constant (site-saturated condition). The model produced a mathematical formulation which captured the initial and evolving microstructural entities and linked their effects to measurable macroscopic variables (e.g. stress).

PL

Symulacje komputerowe są doskonałym narzędziem umożliwiającym przewidywanie rozwoju mikrostruktury podczas rekrystalizacji dynamicznej. Automaty komórkowe są jedną z najbardziej efektywnych metod symulowania zjawisk fizycznych zachodzących podczas rekrystalizacji i rozrostu ziaren. W niniejszym artykule obydwa wymienione zjawiska zostały zamodelowane przy wykorzystaniu dwuwymiarowej siatki automatów komórkowych. Dane takie jak czas, wstępna wielkość ziaren oraz wstępna gęstość zarodkowania zostały wykorzystanie do walidacji modelu jako zmienne modelu JMAK (Johnson, Mehl, Avrami, i Kolmogorov). Zgodnie z przyjętymi założeniami, automaty komórkowe okazały się być dogodnym narzędziem symulacji zjawiska dynamicznej rekrystalizacji.

20

Cellular Automata Simulations for the System of Two - Level Atoms Placed in Two - Dimensional Cavity

51%

Nguyen T. V. , Bui D. T. , Cao Long C. L. , Leoński W.

|

tom Vol. 19, No. 4

189--194

EN

In this paper, using one of the most effective simulation methods, namely the cellular automata formalism, we simulate the dynamics of a system which is composed of a large number of two-level atoms placed in a two-dimensional cavity. We suppose additionally that the cavity is confined by four semi-transparent “mirrors”. We show that similarly to the one-dimensional case, several interesting effects including the molasses effect occur in the considered system.