Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
POZNANUNIVERSITYOFTECHNOLOGYACADEMICJOURNALS
No61
ElectricalEngineering
2010
AnnaPORĘBSKA*
SEARCHINGTHESPACEOFCELLULARAUTOMATA
BASINGONTHEANALYSIS
OFTHECONNECTIONSGRAPHS
Thepaperdescribestheideaofsearchingthespaceof2Dcellularautomatarulesusing
thegraphsofconnections.Nodesarethe“one”cellsintheconfigurationsforwhichthe
ruletakesthevalue“1”.Branchesofagraphconnectall“ones”ingivenconfiguration.The
samegraphwhenonlyrotatedormirrorreflectedisconnectedwithgroupofrules,which
generatethesamebehaviourofthecellularautomaton.Thankstothatthecomputer
investigationofautomataspace,inordertoextractautomatawithinterestingbehaviour,
canbereducedtotestrepresentativesofdistinguishgroups.
1.INTRODUCTION
TheCellularAutomata(CA)areparallelstructures,processinginitialstateaccording
tothetransitionfunction(socalledrule)ineachofthecellsanthesametime.Newstate
ofacelldependsonthestateofthecellsintheneighbourhood.Thetimeandthestates
spacearediscrete.Cellularautomataareusefulformodellingglobalprocessesthatoccur
inlargestructuresoflocallycoupledelements[1].Especiallyforimageprocessing,
wavespropagationmodelling,robotics[3],geneticnetworkmodelling[6],crystallisation
processmodelling[2]etc.Furthermore,itisinterestingtocreatesuchcellularautomata
whichevolveappropriatetotheinitialexcitationinaspecialmanner.However,onlythe
smallpartofthespaceofcellularautomataisnontrivialornon-chaoticandbelongstothe
Wolframclass3(savestheinformation)[7].
Theknowledgeofthetransitionfunctionisnotsufficienttopredictthefinal
stateofthecellularautomaton.Generallythecomputersimulationenablesusto
observeanautomatonevolutionandclassifyittotheseparateclassinthecellular
automataspace[5].Forwellknown5-elementsvonNeumannneighbourhoodthere
are2
32differentrules.For9-elementsMooreneighbourhoodthereare2502different
rules.Becauseofthattheinvestigationofsuchahugespaceinordertoextract
usefulcellularautomataisdifficult.Itwouldbeeasierifwecouldgrouptherules
inseparateclassesandanalyseonlythesecellularautomatageneratedbyrules
belongingtothedifferentclasses.Itnarrowstheresearchingareabecausethe
cellularautomatawithintheoneclassshouldpresentthesamebehaviour.
---
---
---
---
---
---
---
---
---
---
---
---
---
---
*AGHUniversityofScienceandTechnology.
